FrankFiedler,KaHinLeungandQingXiang OnMathon’sconstructionofmaximalarcsinDesarguesianplanes

Advances in Geometry (de Gruyter 2003

On Mathon’s construction of maximal arcs in Desarguesian planes

Frank Fiedler, Ka Hin Leung and Qing Xiang

Dedicated to Adriano Barlotti on the occasion of his 80th birthday

Abstract.We study the problem of determining the largestdof a non-Denniston maximal arc of degree 2^dgenerated by afp;1g-map in PGð2;2^mÞvia a recent construction of Mathon [9].

On one hand, we show that there arefp;1g-maps that generate non-Denniston maximal arcs of degree 2^ðmþ1Þ=2, wheremd5 is odd. Together with Mathon’s result [9] in themeven case, this shows that there are alwaysfp;1g-maps generating non-Denniston maximal arcs of degree 2^bðmþ2Þ=2cin PGð2;2^mÞ. On the other hand, we prove that the largest degree of a non-Denniston maximal arc in PGð2;2^mÞ constructed using afp;1g-map is less than or equal to 2^m3. We conjecture that this largest degree is actually 2^bðmþ2Þ=2cwhenm>9.

Key words.Arc, linearized polynomial, maximal arc, quadratic form.

1 Introduction

Let PGð2;qÞbe the Desarguesian projective plane of orderq,qa prime power. A set ofkpoints in PGð2;qÞis called aðk;nÞ-arcif nonþ1 points of the set are collinear.

The numbernis usually called thedegreeof the arc.

LetKbe aðk;nÞ-arc in PGð2;qÞ, and letPbe a point inK. Then each of theqþ1 lines throughPcontains at mostn1 points ofK. Therefore

kc1þ ðqþ1Þðn1Þ ¼qnþnq:

Aðk;nÞ-arc is said to be maximalifk¼qnþnq. From the above argument, it is easily seen that any line of PGð2;qÞthat contains a point of a maximal arcKmust contain exactlynpoints of that arc; that is

jLVKj ¼0 orn

for every lineLof PGð2;qÞ. Therefore the degreenof a maximalðqnþnq;nÞ-arc must divideq.

The study of arcs of degree greater than two was started by Barlotti [2]. For q¼2^m, Denniston [3] constructed maximalðqnþnq;nÞ-arcs in PGð2;qÞfor every

n,njq,n<q(see also [6, p. 304]). Thas [10], [11] also gave two other constructions of maximal arcs of certain degrees in PGð2;2^mÞ, where m is even. For odd prime powersq, Ball, Blokhuis and Mazzocca [1] proved that maximal arcs of degreendo not exist in PGð2;qÞ, whenn<q. Recently Mathon [9] gave a new construction of maximal arcs in PGð2;2^mÞthat generalizes the construction of Denniston. We give a brief account of his construction.

LetCbe the set of all conics

F_a;b;l¼ fðx;y;zÞAPGð2;2^mÞ jax²þxyþby²þlz²¼0g

where a;b AF₂m and ax²þxþb is irreducible over F₂^m (that is, Tr₂^m₌₂ðabÞ ¼1, here Tr₂^m₌₂ is the trace map from F₂^m to F₂). For l;l⁰AF₂^m, l0l⁰ we define a composition

F_a;b;llF_a0;b⁰;l⁰ ¼F_ala0;blb⁰;lþl⁰

where

ala⁰¼alþa⁰l⁰

lþl⁰ for anya;a⁰AF₂^m:

A subsetFofCis said to be closedunder the compositionlif for anyF1;F2 AF with F10F2 we haveF1lF2AF. In [9] Mathon proved that the set of points of all conics in a closed set of conics together with the common nucleusF0¼Fa;b;0 ¼ ð0;0;1Þforms a maximal arc in PGð2;2^mÞ. When all conics in a closed set of conics come from a single pencil of conics, Mathon’s construction gives rise to Denniston maximal arcs. In general, Mathon showed that closed sets of conics can be obtained by using linearized polynomials overF₂^m. Specifically, Mathon proved the following theorem.

Theorem 1.1 ([9, Theorem 2.5]). Let pðxÞ ¼Pd1

i¼0 a_ix²ⁱ¹ and qðxÞ ¼Pd1 i¼0 b_ix²ⁱ¹ be polynomials with coe‰cients inF₂^m.For an additive subgroup A of order2^d inF₂^m let F¼ fFpðlÞ;qðlÞ;ljlAAnf0ggHC be a set of conics with common nucleus F₀. If Tr₂^m₌₂ðpðlÞqðlÞÞ ¼1 for every lAAnf0g, then the set of points on all conics in F together with F₀ forms a maximalð2^mþd2^mþ2^d;2^dÞ-arcKinPGð2;2^mÞ.If both

pðxÞ,qðxÞhave dc2,thenKis a Denniston arc.

Hamilton [4] gave the following test for when the arc K in Theorem 1.1 is a Denniston arc.

Theorem 1.2([4, Theorem 2.1]).Let pðxÞand qðxÞbe the same polynomials as given in Theorem 1.1, let A be an additive subgroup of size 2^d inF₂^m, and let K be the maximal arc obtained in Theorem1.1.ThenK is of Denniston type if and only if for alll;l⁰AAnf0g,l0l⁰,bothðpðlÞ þpðl⁰ÞÞ=ðlþl⁰Þand ðqðlÞ þqðl⁰ÞÞ=ðlþl⁰Þare constant.

Mathon posed several problems at the end of his paper [9]. The third problem he posed is: What is the largest d of a non-Denniston maximal arc of degree 2^d gen- erated by afp;qg-map in PGð2;2^mÞvia Theorem 1.1? Whenmis even, Mathon [9]

showed that there exists a non-Denniston maximal arc of degree 2^m=2þ1generated by a fp;1g-map in PGð2;2^mÞ. When mis odd, Hamilton [4] showed that there exists a non-Denniston maximal arc of degree 8 generated by afp;1g-map in PGð2;2^mÞ, where md5. In this paper, we concentrate on the following restricted version of Mathon’s problem: What is the largestdof a non-Denniston maximal arc of degree 2^d generated by afp;1g-map in PGð2;2^mÞvia Theorem 1.1? In Section 2, we show that there are fp;1g-maps that generate non-Denniston maximal arcs of degree 2^ðmþ1Þ=2, where md5 is odd. Together with Mathon’s result [9, Theorem 3.2] in the meven case, this shows that there are alwaysfp;1g-maps generating non-Denniston maximal arcs of degree 2^bðmþ2Þ=2cin PGð2;2^mÞ. In Section 3 we prove that if a maxi- mal arc generated by a fp;1g-map via Theorem 1.1 has degree 2^m1 or 2^m2 and md7, then it is a Denniston maximal arc. Hence whenmd7, the largest degree of a non-Denniston maximal arc constructed using afp;1g-map via Theorem 1.1 is less than or equal to 2^m3. We conjecture that whenm>9, this largest degree is actually 2^bðmþ2Þ=2cand provide some evidence for this conjecture.

2 Maximal arcs in PG(2, 2^m),modd

In this sectionmis always an odd positive integer, andgalways denotes an element ofF₂^mwith Tr₂^m₌₂ðgÞ ¼1. To simplify notation, from now on, we will use Tr in place of Tr₂^m₌₂ if there is no confusion. We start with the following lemma.

Lemma 2.1. Let Sg¼ fxAF2^mjTrðgxþx³Þ ¼0g. Then there exists a choice of gAF2^m such that Sgcontains anF2-subspace A withdimðAÞ ¼^mþ1₂ .

Proof. Let QgðxÞ ¼Trðgxþx³Þ and let V¼F₂^m. The map Qg:V!F₂ is a qua- dratic form onVoverF₂. The corresponding bilinear formBis given byBðx;yÞ ¼ Q_gðxþyÞ Q_gðxÞ Q_gðyÞ ¼Trðx²yþxy²Þ, hence

RadV¼ fxAVjBðx;yÞ ¼0 for eachyAVg

¼ fxAVjTrðx²yþxy²Þ ¼0 for eachyAVg

¼ fxAVjTrðyðx²þ ffiffiffi px

ÞÞ ¼0 for eachyAVg

¼ fxAVjx²¼ ffiffiffi px

g:

Since mis odd, we conclude that RadV ¼F₂. Note that in characteristic 2, the quadratic formQgðxÞis not necessarily zero on RadV. Therefore we define

V₀¼ fxARadVjQ_gðxÞ ¼0g:

This is an F₂-space of dimension equal to dimðRadVÞ or dimðRadVÞ 1. Since TrðgÞ ¼1, we have V0¼RadV¼F₂. Hence rankðQgÞ ¼m1 is even and Qg is

either hyperbolic or elliptic. It is always possible to choosegAF₂^m, with TrðgÞ ¼1, such thatQ_gis hyperbolic on V=V₀. (This can be seen from the weight distribution of the dual of the double-error-correcting BCH code, see [8, p. 451]). With this choice ofg, the maximum dimension of a subspace ofV=V₀ on which Q_g vanishes is^m1₂ . Let Ube such a subspace and letA¼U?V₀. Then dimðAÞ ¼^mþ1₂ andQ_gðxÞvan- ishes onA, henceAHS_g. This completes the proof. r Now letgAF₂^m be chosen such that TrðgÞ ¼1 andSg¼ fxAF₂^mjTrðgxþx³Þ ¼ 0g contains an F₂-subspace A of F₂^m of dimension ^mþ1₂ . Let pðxÞ ¼1þgxþx³. Then we have the following corollary of Theorem 1.1.

Theorem 2.2.The set of points on the conicsF¼ fFpðlÞ;1;ljlAAnf0ggtogether with the common nucleus F₀ forms a maximal arcKinPGð2;2^mÞof degree2^ðmþ1Þ=2.When md5,the maximal arcKis non-Denniston.

Proof.Let pðlÞ ¼1þglþl³, with the choice ofgas above, and letAbe the^mþ1₂ - dimensional F₂-subspace in S_g given by Lemma 2.1. Then we have TrðpðlÞÞ ¼ Trð1Þ ¼1 for everylAAnf0g. By Theorem 1.1, the first part of the theorem follows.

Whenmd5, the maximal arc Kis non-Denniston. This can be seen as follows.

For l;l⁰AAnf0g, ðpðlÞ þpðl⁰ÞÞ=ðlþl⁰Þ ¼gþl²þll⁰þl⁰². When jAjd8, this expression cannot be constant when l;l⁰,l0l⁰, run throughAnf0g. Therefore by

Theorem 1.2, the arcKis not of Denniston type. r

Theorem 2.2 together with Mathon’s result ([9, Theorem 3.2]) in themeven case shows that there are alwaysfp;1g-maps generating non-Denniston maximal arcs of degree 2^bðmþ2Þ=2cin PGð2;2^mÞ, whenmd5.

3 Some upper bounds on the degree of non-Denniston maximal arcs from {p, 1}-maps

We start this section by making some remarks about Theorem 1.1. In Theorem 1.1, Mathon restricted the degrees of the polynomials pðlÞ,qðlÞto be less than or equal to 2^d11, where the subspace AHF₂^m involved has size 2^d. We will show that there is no loss of generality in doing so.

Proposition 3.1.Let fðxÞ ¼Pm1

i¼0 aix²ⁱ¹AF2^m½x,and let A be anF2-subspace inF2^m

of size 2^d, where dcm1.Then there exists a polynomial f₁ðxÞ ¼Pd1

i¼0 b_ix²ⁱ¹A F₂^m½xsuch that fðlÞ ¼ f₁ðlÞfor everylAAnf0g.

Proof.Let AðxÞ ¼Q

lAAðxlÞ. This is a degree 2^d linearized polynomial inF₂^m½x (see [7, p. 110], also [8, p. 119]), that is,

AðxÞ ¼x^2dþcd1x^2d1þ þc0x;

whereciAF₂^m. LetaðxÞ ¼x^dþcd1x^d1þ þc0. The polynomialsAðxÞandaðxÞ are called 2-associatesof each other (see [7, p. 115]). LetfðxÞ ¼GðxÞ=x, whereGðxÞ ¼

Pm1

i¼0 a_ix²ⁱ, and letgðxÞ ¼Pm1

i¼0 a_ixⁱ be the 2-associate ofGðxÞ. Using the division algorithm, we write

gðxÞ ¼kðxÞaðxÞ þrðxÞ; ð3:1Þ

where degrðxÞ<degaðxÞ ¼d. Let KðxÞ and RðxÞ be the 2-associates of kðxÞand rðxÞ respectively. Turning (3.1) into linearized 2-associates, and noting that the 2- associate ofkðxÞaðxÞisKðAðxÞÞ, the composition ofAðxÞwithKðxÞ(cf. [7, p. 115], Lemma 3.59), we get

GðxÞ ¼KðAðxÞÞ þRðxÞ; ð3:2Þ

with degRðxÞc2^d1. With f₁ðxÞ ¼RðxÞ=x, we see from (3.2) that fðlÞ ¼ f₁ðlÞfor

everylAAnf0g. r

We note that if one does not restrict the degree of the polynomials pðxÞ,qðxÞto be less than or equal to 2^d11 (where 2^d ¼ jAj), Theorem 1.1 still holds, but then it sometimes leads to Denniston maximal arcs, which, at first sight, may not look like Denniston. We give a couple of examples of this situation below. So by restricting the degrees of the polynomials pðxÞ, qðxÞto be less than or equal to 2^d11 in Theo- rem 1.1, not only is there no loss of generality (by Proposition 3.1), but also some

‘‘trivial’’ examples are avoided.

Example 3.2. Let pðxÞ ¼a0þ^{xþx2þx4þþx}_x ^2m1 AF2^m½x, where Trða0Þ ¼1. Let A¼ fxAF2^mjTrðxÞ ¼0g. Then we have TrðpðlÞÞ ¼1 for every lAAnf0g. This pðxÞ indeed gives rise to a maximal arc of degree 2^m1 in PGð2;2^mÞ by Mathon’s con- struction. But the maximal arc in this example is of Denniston type by Theorem 1.2 since for everylAAnf0g, we have pðlÞ ¼a0, a constant.

Example 3.3. Let pðxÞ ¼Pm1

i¼0 a_ix²ⁱ¹AF₂^m½x, where Trða0Þ ¼1. We may choose a1;a2;. . .;am1AF₂^m such that A¼ flAF₂^mja1l²þa2l²²þ þam1l^2m1¼0g has dimensionm2 overF₂. Then we have TrðpðlÞÞ ¼1 for everylAAnf0g. This pðxÞgives rise to a maximal arc of degree 2^m2 in PGð2;2^mÞby Mathon’s construc- tion. But the maximal arc in this example is again of Denniston type by Theorem 1.2 since for everylAAnf0g, pðlÞ ¼a₀, a constant.

Next we prove that whenmd5 the largest dof a non-Denniston maximal arc of degree 2^d generated by afp;1g-map via Theorem 1.1 is less thanm1.

Theorem 3.4. Let A be an additive subgroup of size 2^m1 in F₂^m, where md5.

Let pðxÞ ¼Pm2

i¼0 a_ix²ⁱ¹AF₂^m½x. If TrðpðlÞÞ ¼1 for all lAAnf0g, then a₂ ¼ a₃¼ ¼am2¼0,thus pðxÞis linear and the maximal arc obtained via Theorem1.1 is of Denniston type.

Proof. Every hyperplane in F₂^m can be written as fxAF₂^mjTrðaxÞ ¼0g for some nonzeroaAF₂^m. By making a change of variable in pðxÞ, we may assume thatA¼ fxAF₂^mjTrðxÞ ¼0g. We consider two cases.

Case 1: Trða0Þ ¼1. In this case, if TrðpðlÞÞ ¼1 for all lAAnf0g, then TrðPm2

i¼1 ail²ⁱ¹Þ ¼0 for alllAAnf0g. Thus,ð1þTrðxÞÞTrðPm2

i¼1 aix²ⁱ¹Þ, viewed as a function fromF₂^m to itself, is identically zero. That is, inF₂^m½x, we have

ð1þTrðxÞÞ Tr X^m2

i¼1

a_ix²ⁱ¹

10 ðmodx^2mxÞ ð3:3Þ

LettðxÞ ¼LHS ofð3:3Þ ¼ ð1þxþx²þ þx^2m1ÞTrðPm2

i¼1 a_ix²ⁱ¹Þ.

Claim: The coe‰cient ofx^2m2rþ2intðxÞisa_mr^2r þa_mrþ1^2r for 3crcm2.

Them-bit binary representation of 2^m2^rþ2 is 1. . .1

|fflffl{zfflffl}

mrd2

0. . .0

|fflffl{zfflffl}

r2d1

10;

which contains two blocks of 1’s (separated by 0’s). (We will always number the bits from right to left as 0;1;2;. . .;m1.) Note that the exponents of the summands in 1þTrðxÞ, written in m-bit binary representation, are 000. . .000, 000. . .001,

000. . .010;. . .;100. . .000, and the exponents of the summands in TrðPm2

i¼1 aix²ⁱ¹Þ are cyclic shifts of

000. . .001;000. . .011;000. . .0111;000. . .01111;. . . and 00

|{z}2

11. . .111

|fflfflfflfflfflffl{zfflfflfflfflfflffl}

m2

:

When we multiply 1þTrðxÞwith TrðPm2

i¼1 a_ix²ⁱ¹Þ, there are two ways to obtain x^2m2rþ2, namely adding the exponent of a summand in 1þTrðxÞ to the exponent of a summand in TrðPm2

i¼1 aix²ⁱ¹Þwith or without carry.

Suppose that we are in the latter case. The exponent from 1þTrðxÞ must be 2 while the exponent from TrðPm2

i¼1 a_ix²ⁱ¹Þis a shift of 2^mr1.

1. . .1

|fflffl{zfflffl}

mrd2

0. . .010¼0. . .010þ1|fflffl{zfflffl}. . .1

mrd2

0. . .0

|fflffl{zfflffl}

r

Thus, this case contributes the coe‰cienta_mr^2r .

Now suppose that we are in the former case. Since bit-1 of 2^m2^rþ2 is 1 while bit-0 is 0, the exponent 2^m2^rþ2 must be obtained as 2⁰ added to ð2^m2^rÞ þ ð2¹2⁰Þ:

1. . .1

|fflffl{zfflffl}

mrd2

0. . .010¼0. . .01þ1|fflffl{zfflffl}. . .1

mrd2

0. . .01;

so this case contributes the coe‰cient a_mrþ1^2r . The claim now follows. In particular, by (3.3), we find thata₂¼a₃¼ ¼a_m2.

Claim: The coe‰cient ofx^2m4intðxÞisa_m2⁴ þa⁴_m3þa_m3⁸ . Clearly the exponentð2^m4Þ ¼11. . .100 can be obtained by

11. . .100¼00. . .000þ11. . .100 This contributes the coe‰cienta_m2⁴ .

Also the exponent 2^m4 can be obtained by adding a non-zero exponent in 1þTrðxÞ to an exponent from TrðPm2

i¼2 aix²ⁱ¹Þ. Suppose that when adding the exponents, there is no carry. We have two ways to obtain 2^m4, namely,

11. . .100¼10. . .0þ011. . .100;

11. . .100¼0. . .0100þ11. . .1000:

This contributes the coe‰cienta⁴_m3þa_m3⁸ . Finally we note that there is no way of getting 2^m4 as a sum of exponents inducing a carry. Thus, the coe‰cient ofx^2m4 in tðxÞis as claimed. This implies am3¼0, which yields a2¼a3 ¼ ¼am2¼0.

Hence pðlÞ ¼a0þa1l.

Case 2: Trða0Þ ¼0. We have TrðPm2

i¼1 a_il²ⁱ¹Þ ¼1 for all lAAnf0g. Hence ð1þTrðxÞÞ ð1þTrðPm2

i¼1 a_ix²ⁱ¹ÞÞ, viewed as a function from F₂^m to itself, is the characteristic function of the subsetf0gofF₂^m. Therefore,

ð1þTrðxÞÞ þ ð1þTrðxÞÞ Tr X^m2

i¼1

aix²ⁱ¹

11x^2m1 ðmodx^2mxÞ ð3:4Þ Note that the binary representation of the exponent of x^2m1 is 111. . .1 (m ones altogether), while in the left hand side of (3.4), the binary representation of the exponent of any term in the product ð1þTrðxÞÞ TrðPm2

i¼1 aix²ⁱ¹Þ cannot have more than 1þ ðm2Þ ¼m1 ones. So (3.4) cannot hold. Thus, this case does not

occur. This completes our proof. r

Remarks.(1) Theorem 3.4 is not true whenm¼4. In PGð2;16Þ, there exists a degree 8 non-Denniston maximal arc (cf. Section 4.1 of [9]).

(2) It is interesting to note that whenmd5 a non-Denniston maximal arc of degree 2^m1 (i.e., the dual of a hyperoval) in PGð2;2^mÞcan be obtained fromfp;qg-maps via Theorem 1.1, withqðxÞ01. See [9, p. 362] for an example in PGð2;32Þ. Theorem 3.4 shows that this cannot be achieved ifmd5 andqðxÞis restricted to be 1.

The ideas in the proof of Theorem 3.4 can be further used to prove the following theorem. The proof contains more complicated computations.

Theorem 3.5. Let A be an additive subgroup of size 2^m2 in F₂^m, where md7. Let pðxÞ ¼Pm3

i¼0 a_ix²ⁱ¹AF₂^m½x. If TrðpðlÞÞ ¼1 for all lAAnf0g then a₂¼a₃¼ ¼am3¼0,thus pðxÞis linear and the maximal arc obtained via Theo- rem1.1is of Denniston type.

Proof. Since A has dimension m2 over F₂, we may assume that A¼ fxAF₂^mj TrðxÞ ¼0 and TrðmxÞ ¼0g for some mAF₂m with m01. Again we consider two cases.

Case1: Trða0Þ ¼1. Then

ð1þTrðxÞÞð1þTrðmxÞÞTr X^m3

i¼1

aix²ⁱ¹

10 ðmodx^2mxÞ

ð1þTrðxÞ þTrðmxÞ þTrðxÞTrðmxÞÞ Tr X^m3

i¼1

a_ix²ⁱ¹

10 ðmodx^2mxÞ ð3:5Þ

Let rðxÞ denote the LHS of (3.5), sðxÞ ¼1þTrðxÞ þTrðmxÞ þTrðxÞTrðmxÞ, and tðxÞ ¼TrðPm3

i¼1 aix²ⁱ¹Þ. The exponent of each term inrðxÞis a sum of the exponent of a summand in sðxÞ and the exponent of some summand in tðxÞ. Similar to the proof of Theorem 3.4, exponents of the summands intðxÞare 2ⁱ1, 1cicm3, and their cyclic shifts. Exponents fromsðxÞare 0; 2ⁱ; and 2ⁱþ2^j,i0j. The termsx⁰, x²ⁱ, and x^2iþ2j ði0jÞ in sðxÞ have coe‰cients 1, 1þm²ⁱþm²ⁱ¹, and m²ⁱþm^2j, respectively.

Claim: The coe‰cient ofx^{ð2m1Þ2m22m4} inrðxÞis

a²_m3^m1ð1þm^2m3þm^2m4Þ þam4ðm^2m1þm^2m3Þ þa_m4^2m1ðm^2m3þm^2m5Þ þam3ðm^2m1þm^2m4Þ:

The binary representation of the exponent of any term in rðxÞcannot have more than 2þ ðm3Þ ¼m1 ones. The binary expansion ofð2^m1Þ 2^m22^m4 is 101011. . .1. This involvesm2 ones, so it can be obtained as a sum of two expo- nents (one fromsðxÞ, the other from tðxÞ) without carry or with exactlyone carry.

Assume that we are in the former case. There are only three ways to obtainð2^m1Þ 2^m22^m4, namely,

101011. . .1¼001000. . .0þ100011. . .1

¼101000. . .0þ000011. . .1

¼001010. . .0þ100001. . .1:

These contribute the coe‰cient ð1þm^2m3þm^2m4Þa_m3^2m1þ ðm^2m1þm^2m3Þam4þ ðm^2m3þm^2m5Þa_m4^2m1 for x^{ð2m1Þ2m22m4} in rðxÞ. (Here we used the assumption that md7. If m¼5, the coe‰cient of the term x^24þ22þ1 in rðxÞ is not the same as in our claim. The reason is that, for example, 10101¼00100þ10001 leads to another possibility, namely 00100 comes from a₁⁴x⁴ in tðxÞ, and 10001 comes from ðm²⁰þm²⁴Þx^20þ24insðxÞ. This cannot happen ifmd7.)

Now assume that a carry had been induced. The last carry-over must have occurred either at bit-ðm3Þor bit-ðm1Þ. The latter case cannot occur.

10101. . .1¼10010. . .0þ0001. . .1:

This contributes the coe‰cientðm^2m1þm^2m4Þam3. This proves the claim. By (3.5), we have

a_m3^2m1ð1þm^2m3þm^2m4Þ þam4ðm^2m1þm^2m3Þ

þa_m4^2m1ðm^2m3þm^2m5Þ þam3ðm^2m1þm^2m4Þ ¼0 ð3:6Þ Claim: The coe‰cient ofx^{ð2m1Þ2m12m4} is

am4ðm^2m2þm^2m3Þ þam3ðm^2m2þm^2m4Þ:

The binary expansion of ð2^m1Þ 2^m12^m4 is 011011. . .1. Suppose it is obtained as a sum of exponents fromsðxÞandtðxÞwithout carry. Then

01101. . .1¼0110. . .0þ00001. . .1

which contributesðm^2m2þm^2m3Þam4. (Here again we have used the assumption that md7. Ifm¼6, the coe‰cient of the termx^24þ23þ2þ1inrðxÞis not the same as in our claim. The reason is that 011011¼011000þ000011 leads to another possibility, namely 011000 comes froma₂⁸x^24þ23 intðxÞ, and 000011 comes fromðm²⁰þm²Þx^20þ2 insðxÞ. This cannot happen ifmd7.)

If ð2^m1Þ 2^m12^m4 is obtained as a sum of exponents from sðxÞand tðxÞ with a carry, the last carry-over must occur at bit-ðm2Þor bit-0.

01101. . .1¼01010. . .00þ00011. . .11:

This contributes the coe‰cient ðm^2m2þm^2m4Þam3. Therefore the claim is proved, and by (3.5), we have

a_m4ðm^2m2þm^2m3Þ ¼a_m3ðm^2m2þm^2m4Þ: ð3:7Þ Claim:a_m3^2m1ð1þm^2m3þm^2m4Þ þa_m4^2m1ðm^2m3þm^2m5Þ ¼0.

The claim is equivalent to

am3ð1þm^2m2þm^2m3Þ þam4ðm^2m2þm^2m4Þ ¼0:

Consider the expression

E¼ ðam3ð1þm^2m2þm^2m3Þ þa_m4ðm^2m2þm^2m4ÞÞðm^2m2þm^2m3Þ

¼am3ðm^2m2þm^2m3Þ þam3ðm^2m2þm^2m3Þ² þam4ðm^2m2þm^2m4Þðm^2m2þm^2m3Þ:

Using (3.7), we have

E¼am3ðm^2m2þm^2m3Þ þam3ðm^2m1þm^2m2Þ þam3ðm^2m2þm^2m4Þ²

¼0:

Since m00;1 we have ðm^2m2þm^2m3Þ00 and our claim follows. In particular, by (3.6) it implies am4ðm^2m1þm^2m3Þ ¼am3ðm^2m1þm^2m4Þ. Adding this to (3.7) we get

am4ðm^2m1þm^2m2Þ ¼am3ðm^2m1þm^2m2Þ:

Henceam4¼am3. Substitutingam4in (3.7) byam3, we haveam3¼0.

Claim: Letm4>k>2. Ifaj¼0 for allm3> j>kthenak ¼0.

We will use a similar argument to that in (3.7). To this end we consider the coe‰cient of x^{ð2k1Þþ2m2þ2m3} in rðxÞ. The binary expansion of its exponent is

0110. . .01. . .1. This includes 2þk ones. All a_j with j>k are zero. The sum

of an exponent from 1þTrðxÞ þTrðmxÞ þTrðxÞTrðmxÞ and an exponent from TrðPk

i¼0aix²ⁱ¹Þhas at most 2þkones. Sincek>2 there is only one way to obtain ð2^k1Þ þ2^m2þ2^m3, namely,

0110. . .0 1|fflffl{zfflffl}. . .1

k>2

¼0110. . .0þ0. . .0 1|fflffl{zfflffl}. . .1

k>2

:

It follows thatðm^2m2þm^2m3Þak ¼0. Henceak¼0.

Sinceam3¼am4¼0 we find thata3¼ ¼am4 ¼am3¼0 by induction.

Claim:a2¼0.

Consider the coe‰cients of x^24þ7 and x^25þ7. Since for all j>2 we have aj¼0 there are only two ways to obtain each exponent.

0. . .0010111¼0. . .0010100þ0. . .0000011

¼0. . .0010001þ0. . .0000110

0. . .0100111¼0. . .0100100þ0. . .0000011

¼0. . .0100001þ0. . .0000110:

Hence the coe‰cient of x^24þ7 is ðm⁴þm¹⁶Þa2þ ðmþm¹⁶Þa₂² and the coe‰cient of x^25þ7isðm⁴þm³²Þa2þ ðmþm³²Þa₂². Adding both values we find

a2ðm¹⁶þm³²Þ þa²₂ðm¹⁶þm³²Þ ¼0:

Thus,a₂is either 0 or 1. Now look at the coe‰cient ofx¹⁵. There are only three ways of obtaining 15 as a sum with the exponents we can use.

0. . .01111¼0. . .01100þ0. . .00011

¼0. . .01001þ0. . .00110

¼0. . .00011þ0. . .01100:

Henceðm⁴þm⁸Þa2þ ðmþm⁸Þa₂²þ ðmþm²Þa⁴₂ ¼0. Ifa₂¼1 thenm²þm⁴ ¼0 which is a contradiction. Thus,a2¼0.

It follows thata2¼ ¼am3 ¼0.

Case2: Trða0Þ ¼0. Then TrðPm3

i¼1 ail²ⁱ¹Þ ¼1 for alllAAnf0g. Hence if we view ð1þTrðxÞ þTrðmxÞ þTrðxÞTrðmxÞÞ

1þTr X^m3

i¼1

aix²ⁱ¹

as a function fromF₂^m to itself, it is the characteristic function of the subsetf0gof F₂^m. Therefore,

ð1þTrðxÞ þTrðmxÞ þTrðxÞTrðmxÞÞ þ ð1þTrðxÞ þTrðmxÞ þTrðxÞTrðmxÞÞ TrX^m3

i¼1

aix²ⁱ¹

11x^2m1 ðmodx^2mxÞ: ð3:8Þ Note that the binary representation of the exponent of x^2m1 is 111. . .1 (m ones altogether), while in the left hand side of (3.8), the binary representation of the exponent of any term in the product

ð1þTrðxÞ þTrðmxÞ þTrðxÞTrðmxÞÞ TrX^m3

i¼1

aix²ⁱ¹

cannot have more than 2þ ðm3Þ ¼m1 ones. So (3.8) cannot hold. Thus, this

case does not occur. This completes our proof. r

Combining Theorem 3.4 and Theorem 3.5 with the constructive result in Section 2 and Theorem 3.2 in [9], we find that when md7, the largestd of a non-Denniston maximal arc of degree 2^d in PGð2;2^mÞgenerated by afp;1g-map via Theorem 1.1 satisfies

mþ2 2

cdcm3:

We have the following conjecture.

Conjecture 3.6.When m>9,the largest d of a non-Denniston maximal arc of degree 2^d inPGð2;2^mÞgenerated by afp;1g-map via Theorem1.1is ^mþ2₂

.

In order to prove the above conjecture, it su‰ces to prove the following. Let A be an additive subgroup in F₂^m of size 2^d, where m>9, pðxÞ ¼a₀þa₁xþ þ ad1x^2d11 AF₂^m½x. Ifdd ^mþ2₂

þ1, TrðpðlÞÞ ¼1 for every lAAnf0g, thena₂ ¼ a₃¼ ¼ad1¼0. So far we can only prove some partial results in this direction.

Theorem 3.7.Let A be an additive subgroup inF₂^m of size2^d,where dcm1,and let pðxÞ ¼a0þa1xþ þad2x^2d21AF2^m½x, with ad200. If TrðpðlÞÞ ¼1 for everylAAnf0g,then dc^mþ2₂ .

Proof.Assume to the contrary thatd >^mþ2₂ ; we will show thatad2¼0. Assume that the defining equation forAis

ð1þTrðm₁xÞÞð1þTrðm₂xÞÞ. . .ð1þTrðm_mdxÞÞ ¼1;

where m_iAF₂^m, i¼1;2;. . .;md, are linearly independent over F₂. We consider two cases:

Case1: Trða0Þ ¼1. Then

ð1þTrðm₁xÞÞð1þTrðm₂xÞÞ. . .ð1þTrðm_mdxÞÞ TrX^d2

i¼1

a_ix²ⁱ¹

10 ðmodx^2mxÞ: ð3:9Þ

Claim: The coe‰cient ofx^{1þ2þ22þþ2d3þ2d1þ2dþþ2m2} is X

sASmd

m_sð1Þ^2m2m_sð2Þ^2m3. . .m²_sðmdÞ^d1

ad2;

whereSmd is the symmetric group onmd letters.

The exponent ofx^{1þ2þ22þþ2d3þ2d1þ2dþþ2m2} hasm-bit binary representation 0 11|fflfflffl{zfflfflffl}. . .1

md

0 11|fflfflffl{zfflfflffl}. . .1

d2

:

Since d >^mþ2₂ , we see that d2>md, there is only one way to get the term x^{1þ2þ22þþ2d3þ2d1þ2dþþ2m2} when multiplying ð1þTrðm₁xÞÞð1þTrðm₂xÞÞ. . . ð1þTrðm_mdxÞÞwith TrðPd2

i¼1 aix²ⁱ¹Þ, namely 0 11. . .1

|fflfflffl{zfflfflffl}

md

0 11. . .1

|fflfflffl{zfflfflffl}

d2

¼0 00. . .0

|fflfflffl{zfflfflffl}

md

0 11. . .1

|fflfflffl{zfflfflffl}

d2

þ0 11. . .1

|fflfflffl{zfflfflffl}

md

0 00. . .0

|fflfflffl{zfflfflffl}

d2

:

Therefore the claim follows. By (3.9), we see that

X

sASmd

m_sð1Þ^2m2m_sð2Þ^2m3. . .m_sðmdÞ^2d1

ad2¼0: ð3:10Þ

Now setr¼md. Then X

sASmd

m_sð1Þ^2m2m_sð2Þ^2m3. . .m_sðmdÞ^2d1 ¼ X

sASr

m_sð1Þ^2r1m_sð2Þ^2r2. . .m_sðrÞ 2^d1

:

Note that

X

sASr

m²_sð1Þ^r1m_sð2Þ^2r2. . .m_sðrÞ¼det

m₁ m₂ m_r m²₁ m₂² m_r²

m₁^2r1 m₂^2r1 m_r^2r1 0

BB B@

1 CC CA:

We will useDðm₁;m₂;. . .;m_rÞto denote this last determinant. Sincem_i,i¼1;2;. . .; r, are linearly independent overF₂, we see thatDðm₁;m₂;. . .;m_rÞ00 (cf. [7, p. 109]).

By (3.10), this shows thatad2¼0.

Case2: Trða0Þ ¼0. As before, this case can be easily seen not to occur.

This completes the proof. r

In order to extend the result in Theorem 3.7, we need to introduce more notation.

Letm₁;m₂;. . .;m_rbe elements in F₂^m that are linearly independent overF₂. Let 0¼

a₁<a₂< <a_rcm1 be integers. We define Tða1;a2;. . .;arÞ ¼ X

sASr

m_sð1Þ^2a1m_sð2Þ^2a2 . . .m_sðrÞ^2ar:

Using the above notation, we have the following lemma.

Lemma 3.8.Let m>9be an odd integer,let r¼^m3₂ ,and let t be an integer such that 3ctc^m1₂ .Then there exist0¼a1<a2< <arcm1such that

(i) arcmt3,

(ii) Tða1;a₂;. . .;a_rÞ00,and

(iii) the number of consecutive integers in the setfa1;a₂;. . .;a_rgis less than or equal to t1.

We postpone the proof of this lemma to the appendix. With this lemma, we can prove the following theorem.

Theorem 3.9.Let m>9be an odd integer,let A be an additive subgroup inF₂^mof size 2^d, where dcm1, and let pðxÞ ¼a₀þa₁xþa₂x³þ þa_tx^2t1AF₂^m½x, with a_t00 and tcðd1Þ. If 3ctc^m1₂ , and TrðpðlÞÞ ¼1 for every lAAnf0g, then dc^mþ1₂ .

Proof.Assume to the contrary thatd >^mþ1₂ ; we will show thata_t¼0. Without loss of generality, assume thatd¼^mþ3₂ , and letr¼md ¼^m3₂ . Assume that the defin- ing equation forAis

ð1þTrðm₁xÞÞð1þTrðm₂xÞÞ. . .ð1þTrðm_rxÞÞ ¼1;

where m_iAF₂^m,i¼1;2;. . .;r, are linearly independent overF₂. As in the proof of Theorem 3.7, we only need to consider the case where Trða0Þ ¼1. Hence we have

ð1þTrðm₁xÞÞð1þTrðm₂xÞÞ. . .ð1þTrðm_rxÞÞTrX^t

i¼1

a_ix²ⁱ¹

10 ðmodx^2mxÞ:

ð3:11Þ By Lemma 3.8, there exist 0¼a1<a2< <arcm1 such that

(i) arcmt3,

(ii) Tða1;a2;. . .;arÞ00, and

(iii) the number of consecutive integers in the setfa1;a₂;. . .;a_rgis less than or equal tot1.

We will look at the coe‰cient of x^{1þ2a2þþ2arþ2m2þ2m3þþ2mt1} in the left hand side of (3.11). Note that the exponent of this monomial has them-bit binary repre- sentation

0 11|fflfflffl{zfflfflffl}. . .1

t

0 0|fflfflfflfflfflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflfflfflfflfflffl}. . .1. . .1. . .1

mt2

;

where at theaith bit there is a 1, for eachi¼1;2;. . .;r.

Since the number of consecutive integers in the set fa1;a2;. . .;arg is less than or equal tot1, there is only one way to get the term

x^{1þ2a2þþ2arþ2m2þ2m3þþ2mt1} when multiplying

ð1þTrðm₁xÞÞð1þTrðm₂xÞÞ. . .ð1þTrðm_rxÞÞ with TrðPt

i¼1a_ix²ⁱ¹Þ, namely

0 11|fflfflffl{zfflfflffl}. . .1

t

0 0|fflfflfflfflfflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflfflfflfflfflffl}. . .1. . .1. . .1

mt2

¼0 00|fflfflffl{zfflfflffl}. . .0

t

0 0|fflfflfflfflfflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflfflfflfflfflffl}. . .1. . .1. . .1

mt2

þ0 11|fflfflffl{zfflfflffl}. . .1

t

0 00|fflfflffl{zfflfflffl}. . .0

mt2

:

Therefore, the coe‰cient of x^{1þ2a2þþ2arþ2m2þ2m3þþ2mt1} in the left hand side of (3.11) is

X

sASr

m²_sð1Þ^a1m_sð2Þ^2a2 . . .m_sðrÞ^2ar

!

a_t^2mt1¼Tða1;. . .;arÞa²_t^mt1:

By (3.11), we see that Tða1;. . .;arÞa_t^2mt1 ¼0. Since Tða1;. . .;arÞ00, we have

at¼0. This completes the proof. r

4 Appendix

In this appendix, we give a proof of Lemma 3.8. First, we introduce some nota- tion. Letx₁;. . .;x_rbe elements inF₂^m that are linearly independent overF₂. For any integeri, we setv_i¼ ðx²₁ⁱ;. . .;x_r²ⁱÞ. We usev_i^2j to denote component-wise exponentia- tion of v_i by 2^j. Hence v_i^2j ¼viþj. Since x_l^2m¼x_l for all l¼1;2;. . .;r, we have v_m¼v₀. So in what follows, the indices ofv_i are to be read modulom. Now condi- tion (ii) of Lemma 3.8 is equivalent to the vectors

va1;. . .;var

being linearly independent overF₂^m, i.e.,

det

x₁^2a1 x_r^2a1 ...

.. . ... x²₁^ar x²_r^ar 0

B@

1 CA00:

Let V be the F₂^m-span of v0;. . .;vm1. By [7, Lemma 3.51], dimF2mV¼r and fvi;viþ1;. . .;viþr1gis anF₂^m-basis ofVfor any 0cicmr.

In the following, we will be considering subspaces ofVspanned by some vectors

in fv0;v1;. . .;vm1g. To this end, we will use binary vectors to represent subsets of

fv0;. . .;vm1g. Letu¼ ðu0;u1;. . .;ui1Þbe a vector with entries in f0;1g. Then the subset offv0;v1;. . .;vm1grepresented byuis

SðuÞ ¼ fv_lju_l00;0clci1g:

By VðuÞ we will denote the F₂^m-span of the vectors in SðuÞ. For example, if u¼ ð1;1;0;1ÞthenVðuÞ ¼F₂^mv₀þF₂^mv₁þF₂^mv₃. For convenience, we also allow con- catenation of binary vectors. Ifu¼ ðu0;u₁;. . .;ui1Þandu⁰¼ ðu₀⁰;. . .;u_j1⁰ Þthen the concatenation ofuwithu⁰is

uu⁰¼ ðu0;. . .;u_i1;u₀⁰;. . .;u_j1⁰ Þ:

Moreoveru|fflfflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflfflffl}u u

l

is abbreviated tou^l.

Now we can reformulate Lemma 3.8 as follows: For every integer t such that 3ctc^m1₂ , there exists a binary vectoru of length at most m ðtþ2Þ such that VðuÞ ¼V and the number of consecutive 1’s in u is at most t1. It is this refor- mulation that we will prove in this appendix.

One final preparation before we give the proof. Given integers i and j>0, let Iði;jÞdenote theF₂^m-span ofvi,viþ1;. . .;viþj1. Given a subspaceWofV, we define W^2t ¼ fw^2tjwAWg, wherew^2t means component-wise exponentiation of wby 2^t. We will need the following lemma.

Lemma 4.1.Suppose that W¼VðuÞwhereu¼ ðu0;u₁;. . .;us1ÞAF₂^s.If Iðs;tÞHW and W^2tVIð0;sÞHW then W¼V.

Proof. By assumption, Wis spanned by a subset of fv0;. . .;vs1g. LetviAW, 0c ics1, be one of the generating vectors. Ifiþtcs1, thenv_i^2t ¼viþtAIð0;sÞV W^2tHW. Ifiþt>s1, thenv_i^2t ¼viþt AIðs;tÞHW. Hence for any vectorviAW, 0cics1, we haveviþtAW. Extending this property to linear combinations of the generating vectors of W, we see that Iðsþt;tÞHW sinceIðs;tÞHW. That is, Iðsþlt;tÞHW for allld0. HenceviAWfor all 0cicm1 andW ¼V. r Proof of Lemma3.8. Write r¼ktþa where 0cact1. Since r¼^m3₂ , we have m¼2ktþ2aþ3. Seta¼ ð1;1;. . .;1ÞAF₂^a andu¼ ð0;1;. . .;1ÞAF₂^t. Let

VðiÞ ¼VðauⁱÞ:

That is,VðiÞis the space spanned by the vectors inSðauⁱÞ. ThenVðkÞis theF₂^m- span offv0;v1;. . .;vr1gnfva;vaþt;. . .;vaþðk1Þtg. Sincefv0;v1;. . .;vr1gis a basis for V, we see that dimVðkÞ ¼rk. Letbbe the smallest nonnegative integer such that VðkþbÞ ¼Vðkþbþ1Þ. In particular,VðkþiÞis a proper subspace ofVðkþiþ1Þ if 0ci<b. We observe that 0cbck. There are three cases to consider.

Case 1: dimVðkþ1Þdrkþ2. In this case bck1. If VðkþbÞ ¼V, then Sðau^ðkþbÞÞspansV. Note thatau^ðkþbÞhas lengthaþ ðkþbÞtcaþ ð2k1Þt¼ ma ðtþ3Þ. By construction this vector does not have more thant1 consecu- tive 1’s. So we are done in this case.

IfVðkþbÞ0V thenbck2. Let0¼ ð0;0;. . .;0ÞAF₂^t anda⁰¼ ð1;0;. . .;0ÞA F₂^t. Let

wi¼au^ðkþbÞ0a⁰ⁱ:

We define WðiÞ ¼VðwiÞ to be the F₂^m-span of the vectors in SðwiÞ. In par- ticular, Wð0Þ ¼VðkþbÞ. Let b⁰ be the smallest nonnegative integer such that Wðb⁰Þ ¼Wðb⁰þ1Þ.

dimWð0Þ ¼dimVðkþbÞ

ddimVðkþ1Þ þ ðb1Þ drkþ2þb1

¼r ðkb1Þ:

Hence 0cb⁰ck1b. We claim that (i) Wðb⁰ÞIIðaþ ðbþkþiþ1Þt;tÞ

(ii) Wðb⁰ÞIWðb⁰Þ^2tVIð0;aþ ðbþkþiþ1ÞtÞ

for allid0. By Lemma 4.1, these two claims imply thatWðb⁰Þ ¼V. The length of w_b⁰ is

aþ ðkþbþ1þb⁰Þtcaþ2kt¼ma3:

Note that the last t1 entries in wb⁰ are zero. Dropping these t1 positions we obtain a vector of lengthma ðtþ2Þ. This vector does not have more thant1 consecutive 1’s and it corresponds to a subset of fva1;. . .;v_arg that spans V, hence Lemma 3.8 is proved in this case once we prove the above two claims.

To prove the first claim, we recall that Wðb⁰Þ ¼Vðau^ðkþbÞ0a^0b0Þ. Hence vaþðkþbþ1þiÞtAWðb⁰Þfor allid0 since this vector corresponds to the first position in thei-th copy ofa⁰. NowWðb⁰ÞKVðkþbÞ ¼Vðkþbþ1þiÞfor allid0, we also haveSðau^{ðkþbþ1þiÞ}ÞHWðb⁰Þ. Thus

vaþðkþbþ1þiÞtþ1;. . .;vaþðkþbþ1þiÞtþðt1ÞAWðb⁰Þ;

since these vectors correspond to the nonzero positions in the last copy of u in au^{ðkþbþ2þiÞ}. This proves our first claim.

For the second claim it su‰ces to show that Sð0au^ðkþbÞ0a⁰ⁱÞJWðb⁰Þ.

Hence we need to show that the vectors corresponding to the ðkþbÞ-th copy of u and the i-th copy of a⁰, respectively, are in Wðb⁰Þ. The former is true since Wðb⁰Þincludes Sðau^ðkþbþ1ÞÞwhich spansVðkþbþ1Þ. The latter holds because Wðb⁰Þ ¼Wðb⁰þ1Þ which includes the vectors in Sðau^ðkþbÞ0a^0ðb0þ1Þ). This proves our second claim.

Case 2: dimVðkþ1Þ ¼rkþ1¼dimVðkÞ þ1. In this case, one of the vectors

vrþ1;. . .;vrþðt1Þ does not belong to VðkÞ. Suppose that vector is vrþj ¼vaþktþj,

1cjct1. Then Vðkþ1Þ ¼VðkÞ þF₂^mvrþj. Since any linear dependence rela- tion translates to a linear dependence relation when both sides are raised to the 2^tth power, we get dimVðkþiÞcdimVðkÞ þi,id0.

Subcase1:VðkþbÞ0V, i.e.,b<k. As seen above, all vectorsvrþ1;. . .;vrþðt1Þwere linearly dependent on vectors inVðkÞandvrþj. Any such linear dependence translates to a linear dependence ofvrþðb1Þtþi,i0j, on vectors inVðkþb1Þandvrþðb1Þtþj. Hence the vectorvrþðb1Þtþjmust be a vector amongvrþðb1Þtþ1;. . .;vrþðb1Þtþðt1Þthat is not inVðkþb1Þ. Therefore, we can replace those positions in the last copy ofu in au^ðkþb1Þu that do not correspond to v_{rþðb1Þtþj} by 0; we will denote the modified vector byau^ðkþb1Þu^ðjÞ, whereu^ðjÞcontains only one 1. By our discus- sion above, we see that

VðkþbÞ ¼Vðau^ðkþb1Þu^ðjÞÞ;