Combinatorial geometries representable over GF(3) and GF(q). I. The number of points

Letq be a prime power not divisible by 3. We show that the number of points (or rank-1 flats) in a combinatorial geometry (or simple matroid) of rankn representable over GF(3) and GF(q) is at mostn ². Whenq is odd, this bound is sharp and is attained by the Dowling geometries over the cyclic group of order 2.This research was partially supported by National Science Foundation Grant DMS-8521826 and a North Texas State University Faculty Research Grant.     

Matroids with No (q+2)-Point-Line Minors

It is known that a geometry with rankrand no minor isomorphic to the (q+2)-point line has at most (q^r−1)/(q−1) points, with strictly fewer points ifr>3 andqis not a prime power. Forqnot a prime power andr>3, we show thatq^r−1−1 is an upper bound. Forqa prime power andr>3, we show that any rank-rgeometry with at leastq^r−1points and no (q+2)-point-line minor is representable overGF(q). We strengthen these bounds toq^r−1−(q^r−2−1)/(q−1)−1 andq^r−1−(q^r−2−1)/(q−1) respectively whenqis odd. We give an application to unique representability and a new proof of Tutte's theorem: A matroid is binary if and only if the 4-point line is not a minor.     

Factorization of the Cyclotomic Polynomialx+ 1 over Finite Fields

The aim of this note is to show that the (well-known) factorization of the 2ⁿ⁺¹th cyclotomic polynomialx2ⁿ+ 1 over GF(q) withq≡ 1 (mod 4) can be used to prove the (more complicated) factorization of this polynomial over GF(q) withq≡ 3 (mod 4).     

The Jamison method in galois geometries

In a fundamental paper R.E. Jamison showed, among other things, that any subset of the points of AG(n, q) that intersects all hyperplanes contains at least n(q – 1) + 1 points. Here we show that the method of proof used by Jamison can be applied to several other basic problems in finite geometries of a varied nature. These problems include the celebrated flock theorem and also the characterization of the elements of GF(q) as a set of squares in GF(q ²) with certain properties. This last result, due to A. Blokhuis, settled a well-known conjecture due to J.H. van Lint and the late J. MacWilliams.     

The weight distribution of linear codes over GF(ql) having generator matrix over GF(q>)

We study the weight distribution of the linear codes over GF(q^l) which have generator matrices over GF(q) and their dual codes. As an application we find the weight distribution of the irreducible cyclic (23(2¹≈1), 111) codes over GF(2) for all lnot divisible by 11.     

Representable orientations of the free spikes

All orientations of binary and ternary matroids are representable [R.G. Bland, M. Las Vergnas, Orientability of matroids, J. Combinatorial Theory Ser. B 24 (1) (1978) 94–123; J. Lee, M. Scobee, A characterization of the orientations of ternary matroids, J. Combin. Theory Ser. B 77 (2) (1999) 263–291]. In this paper we show that this is not the case for matroids that are representable over GF(p^k) where k2. Specifically, we show that there are orientations of the rank-k free spike that are not representable for all k4. The proof uses threshold functions to obtain an upper bound on the number of representable orientations of the free spikes.     

New linear codes over GF(8)

Let [n, k, d; q]-codes be linear codes of length n, dimension k and minimum Hamming distance d over GF(q). Let d₈(n, k) be the maximum possible minimum Hamming distance of a linear [n, k, d; 8]-code for given values of n and k. In this paper, eighteen new linear codes over GF(8) are constructed which improve the table of d₈(n, k) by Brouwer.     

Packing problems in Galois geometries over GF(3)

A set of kind s in the Galois space S _r,q is a set of points such that any s+1 are linearly independent but there is at least one subset of s+2 The packing problem is that of finding , the largest size of kind s in S _r,q. The main result is the evaluation of for all sr5. linearly dependent points. Some partial results bounding m ^s _6,3 are also given.     

On the sharpness of a theorem of B. segre

The theorem of B. Segre mentioned in the title states that a complete arc of PG(2,q),q even which is not a hyperoval consists of at mostq−√q+1 points. In the first part of our paper we prove this theorem to be sharp forq=s ² by constructing completeq−√q+1-arcs. Our construction is based on the cyclic partition of PG(2,q) into disjoint Baer-subplanes. (See Bruck [1]). In his paper [5] Kestenband constructed a class of (q−√q+1)-arcs but he did not prove their completeness. In the second part of our paper we discuss the connections between Kestenband’s and our constructions. We prove that these constructions result in isomorphic (q−√q+1)-arcs. The proof of this isomorphism is based on the existence of a traceorthogonal normal basis in GF(q ³) over GF(q), and on a representation of GF(q)³ in GF(q ³)³ indicated in Jamison [4].     

On Unitals ith Many Baer Sublines

We identify the points of PG(2, q) ith the directions of lines in GF(q ³), viewed as a 3-dimensional affine space over GF(q). Within this frameork we associate to a unital in PG(2, q) a certain polynomial in to variables, and show that the combinatorial properties of the unital force certain restrictions on the coefficients of this polynomial. In particular, if q = p ² where p is prime then e show that a unital is classical if and only if at least (q - 2) secant lines meet it in the points of a Baer subline.     

An infinite family of simply connected flag-transitive tilde geometries

We consider tilde-geometries (orT-geometries), which are geometries belonging to diagrams of the following shape: Here the rightmost edge stands for the famous triple cover of the classical generalized quadrangle related to the group Sp₄(2). The automorphism group of the cover is the nonsplit extension 3·Sp₄(2) – 3 ·S ₆. Five examples of flag-transitiveT-geometries were known. These are rank 3 geometries related to the groupsM ₂₄ (the Mathieu group),He (the Held group) and and 3⁷·Sp₆(2) (a nonsplit extension); a rank 4 geometry related to the Conway groupCo ₁ and a rank 5 geometry related to the Fischer-Griess Monster groupF ₁. In the present paper we construct an infinite family of flag-transitiveT-geometries and prove that all the new geometries are simply connected. The automorphism group of the rankn geometry in the family is a nonsplit extension of a 3-group by the symplectic group Sp_2n (2). The rank of the 3-group is equal to the number of 2-dimensional subspaces in ann-dimensional vector space over GF(2).     

Directed graph representation of half-rate additive codes over GF(4)

We show that (n, 2 ⁿ ) additive codes over GF(4) can be represented as directed graphs. This generalizes earlier results on self-dual additive codes over GF(4), which correspond to undirected graphs. Graph representation reduces the complexity of code classification, and enables us to classify additive (n, 2 ⁿ ) codes over GF(4) of length up to 7. From this we also derive classifications of isodual and formally self-dual codes. We introduce new constructions of circulant and bordered circulant directed graph codes, and show that these codes will always be isodual. A computer search of all such codes of length up to 26 reveals that these constructions produce many codes of high minimum distance. In particular, we find new near-extremal formally self-dual codes of length 11 and 13, and isodual codes of length 24, 25, and 26 with better minimum distance than the best known self-dual codes.     

Geometry of Cubic and Quartic Hypersurfaces over Finite Fields

Let YPⁿ be a cubic hypersurface defined over GF(q). Here, we study the Finite Field Nullstellensatz of order [q/3] for the set Y(q) of its GF(q)-points, the existence of linear subspaces of PG(n,q) contained in Y(q) and the possibility to join any two points of Y(q) by the union of two lines of PG(n,q) entirely contained in Y(q). We also study the existence of linear subspaces defined over GF(q) for the intersection of Y with s quadrics and for quartic hypersurfaces.     

Irreducible polynomials over GF(2) with prescribed coefficients

For an even positive integer n, we determine formulas for the number of irreducible polynomials of degree n over GF(2) in which the coefficients of xⁿ⁻¹,xⁿ⁻² and xⁿ⁻³ are specified in advance. Formulas for the number of elements in GF(2ⁿ) with the first three traces specified are also given.     

Maximal sets of non-polar points of quadrics and symplectic polarities over GF(2)

A cap on a non-singular quadric over GF(2) is a set of points that are pairwise non-polar; equivalently the join of any two of the points is a chord. A non-secant set of the quadric is a set of points off the quadric that are pairwise non-polar; equivalently the join of any two of the points is skew to the quadric. We determine all the maximal caps and all the maximal non-secant sets of all non-singular quadrics over GF(2); and also all the maximal sets of non-polar points for symplectic polarities over GF(2). The classification is in terms of caps of greatest size on elliptic quadrics Q _– ^8k+3 (2), hyperbolic quadrics Q ₊ ^8k+7 (2) and on quadrics Q _4k+2(2), and of non-secant sets of greatest size of Q _– ^8k+1 (2), Q ₊ ^8k+5 (2) and Q _4k (2), for all quadrics of these types that occur as sections of the parent quadric or belong to the symplectic polarity. The sets of greatest size for these types of quadrics are larger than for other types. The results have implications about the non-existence of ovoids and the exterior sets of Thas. Only one part of the simple geometric inductive argument extends to larger ground fields.     

Some results concerning cryptographically significant mappings over GF(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

In this paper we investigate the existence of permutation polynomials of the form F(x) = x ^d  + L(x) over GF(2 ⁿ ), L being a linear polynomial. The results we derive have a certain impact on the long-term open problem on the nonexistence of APN permutations over GF(2 ⁿ ), when n is even. It is shown that certain choices of exponent d cannot yield APN permutations for even n. When n is odd, an infinite class of APN permutations may be derived from Gold mapping x ³ in a recursive manner, that is starting with a specific APN permutation on GF(2 ^k ), k odd, APN permutations are derived over GF(2 ^k+2i ) for any i ≥ 1. But it is demonstrated that these classes of functions are simply affine permutations of the inverse coset of the Gold mapping x ³. This essentially excludes the possibility of deriving new EA-inequivalent classes of APN functions by applying the method of Berveglieri et al. (approach proposed at Asiacrypt 2004, see [3]) to arbitrary APN functions.     

Strongly inequivalent representations and Tutte polynomials of matroids

We develop constructive techniques to show that non-isomorphic 3-connected matroids that are representable over a fixed finite field and that have the same Tutte polynomial abound. In particular, for most prime powers q, we construct infinite families of sets of 3-connected matroids for which the matroids in a given set are non-isomorphic, are representable over GF(q), and have the same Tutte polynomial. Furthermore, the cardinalities of the sets of matroids in a given family grow exponentially as a function of rank, and there are many such families.In Memory of Gian-Carlo Rota     

Flag transitive planes of orderq n with a long cyclel ∞ as a collineation

Baker and Ebert [1] presented a method for constructing all flag transitive affine planes of orderq ² havingGF(q) in their kernels for any odd prime powerq. Kantor [6; 7; 8] constructed many classes of nondesarguesian flag transitive affine planes of even order, each admitting a collineation, transitively permuting the points at infinity. In this paper, two classes of non-desarguesian flag transitive affine planes of odd order are constructed. One is a class of planes of orderq ⁿ , whereq is an odd prime power andn 3 such thatq ⁿ 1 (mod 4), havingGF(q) in their kernels. The other is a class of planes of orderq ⁿ , whereq is an odd prime power andn 2 such thatq ⁿ 1 (mod 4), havingGF(q) in their kernels. Since each plane of the former class is of odd dimension over its kernel, it is not isomorphic to any plane constructed by Baker and Ebert [1]. The former class contains a flag transitive affine plane of order 27 constructed by Kuppuswamy Rao and Narayana Rao [9]. Any plane of the latter class of orderq ⁿ such thatn 1 (mod 2), is not isomorphic to any plane constructed by Baker ad Ebert [1].The author is grateful to the referee for many helpful comments.     

Irreducible polynomials over GF(2) with three prescribed coefficients

For an odd positive integer n, we determine formulas for the number of irreducible polynomials of degree n over GF(2) in which the coefficients of xⁿ⁻¹, xⁿ⁻² and xⁿ⁻³ are specified in advance. Formulas for the number of elements in GF(2ⁿ) with the first three traces specified are also given.     

On the Uniqueness of Matroid Representations Over GF(4)

We determine when a matroid is uniquely representable over GF(4).In particular all 3-connected (GF(4)-representable) matroidshave this property.