Cyclotomic integers and finite geometry

Schmidt, Bernhard

doi:10.1090/S0894-0347-99-00298-2

Cyclotomic integers and finite geometry
HTML articles powered by AMS MathViewer

by Bernhard Schmidt

J. Amer. Math. Soc. 12 (1999), 929-952

DOI: https://doi.org/10.1090/S0894-0347-99-00298-2

Published electronically: May 5, 1999

PDF | Request permission

Abstract:

We obtain an upper bound for the absolute value of cyclotomic integers which has strong implications on several combinatorial structures including (relative) difference sets, quasiregular projective planes, planar functions, and group invariant weighing matrices. Our results are of broader applicability than all previously known nonexistence theorems for these combinatorial objects. We will show that the exponent of an abelian group $G$ containing a $(v,k,\lambda ,n)$-difference set cannot exceed $\left (\frac {2^{s-1}F(v,n)}{n}\right )^{1/2}v$ where $s$ is the number of odd prime divisors of $v$ and $F(v,n)$ is a number-theoretic parameter whose order of magnitude usually is the squarefree part of $v$. One of the consequences is that for any finite set $P$ of primes there is a constant $C$ such that $\exp (G)\le C|G|^{1/2}$ for any abelian group $G$ containing a Hadamard difference set whose order is a product of powers of primes in $P$. Furthermore, we are able to verify Ryser’s conjecture for most parameter series of known difference sets. This includes a striking progress towards the circulant Hadamard matrix conjecture. A computer search shows that there is no Barker sequence of length $l$ with $13<l\le 4\cdot 10^{12}$. Finally, we obtain new necessary conditions for the existence of quasiregular projective planes and group invariant weighing matrices including asymptotic exponent bounds for cases which previously had been completely intractable.

References

K. T. Arasu, James A. Davis, and J. Jedwab, A nonexistence result for abelian Menon difference sets using perfect binary arrays, Combinatorica 15 (1995), no. 3, 311–317. MR 1357278, DOI 10.1007/BF01299738
K. T. Arasu, James A. Davis, Jonathan Jedwab, Siu Lun Ma, and Robert L. McFarland, Exponent bounds for a family of abelian difference sets, Groups, difference sets, and the Monster (Columbus, OH, 1993) Ohio State Univ. Math. Res. Inst. Publ., vol. 4, de Gruyter, Berlin, 1996, pp. 129–143. MR 1400414, DOI 10.1007/BF02437396
K. T. Arasu and Qing Xiang, Multiplier theorems, J. Combin. Des. 3 (1995), no. 4, 257–268. MR 1333297, DOI 10.1002/jcd.3180030403
Leonard D. Baumert, Cyclic difference sets, Lecture Notes in Mathematics, Vol. 182, Springer-Verlag, Berlin-New York, 1971. MR 0282863
Thomas Beth, Dieter Jungnickel, and Hanfried Lenz, Design theory, Cambridge University Press, Cambridge, 1986. MR 890103
A. I. Borevich and I. R. Shafarevich, Number theory, Pure and Applied Mathematics, Vol. 20, Academic Press, New York-London, 1966. Translated from the Russian by Newcomb Greenleaf. MR 0195803
W. K. Chan, Necessary conditions for Menon difference sets, Des. Codes Cryptogr. 3 (1993), no. 2, 147–154. MR 1218947, DOI 10.1007/BF01388413
Wai-Kiu Chan, Man Keung Siu, and Siu Lun Ma, Nonexistence of certain perfect arrays, Discrete Math. 125 (1994), no. 1-3, 107–113. 13th British Combinatorial Conference (Guildford, 1991). MR 1263738, DOI 10.1016/0012-365X(94)90150-3
Yu Qing Chen, On the existence of abelian Hadamard difference sets and a new family of difference sets, Finite Fields Appl. 3 (1997), no. 3, 234–256. MR 1459826, DOI 10.1006/ffta.1997.0184
R. Craigen, The structure of weighing matrices having large weights, Des. Codes Cryptogr. 5 (1995), no. 3, 199–216. MR 1322815, DOI 10.1007/BF01388384
R. Craigen and H. Kharaghani, Hadamard matrices from weighing matrices via signed groups, Des. Codes Cryptogr. 12 (1997), no. 1, 49–58. MR 1462521, DOI 10.1023/A:1008241809111
J.A. Davis, J. Jedwab: A unifying construction of difference sets. Technical Report HPL-96-31, Hewlett-Packard Labs., Bristol (1996).
James A. Davis and Jonathan Jedwab, Nested Hadamard difference sets, J. Statist. Plann. Inference 62 (1997), no. 1, 13–20. MR 1463370, DOI 10.1016/S0378-3758(96)00162-0
Peter Dembowski and Fred Piper, Quasiregular collineation groups of finite projective planes, Math. Z. 99 (1967), 53–75. MR 215741, DOI 10.1007/BF01118689
Peter Eades and Richard M. Hain, On circulant weighing matrices, Ars Combin. 2 (1976), 265–284. MR 434844
Shalom Eliahou and Michel Kervaire, Barker sequences and difference sets, Enseign. Math. (2) 38 (1992), no. 3-4, 345–382. MR 1189012
Shalom Eliahou, Michel Kervaire, and Bahman Saffari, A new restriction on the lengths of Golay complementary sequences, J. Combin. Theory Ser. A 55 (1990), no. 1, 49–59. MR 1070014, DOI 10.1016/0097-3165(90)90046-Y
Michael J. Ganley, On a paper of P. Dembowski and T. G. Ostrom: “Planes of order $n$ with collineation groups of order $n^{2}$” (Math. Z. 103 (1968), 239–258), Arch. Math. (Basel) 27 (1976), no. 1, 93–98. MR 425763, DOI 10.1007/BF01224646
Anthony V. Geramita, Joan Murphy Geramita, and Jennifer Seberry Wallis, Orthogonal designs, Linear and Multilinear Algebra 3 (1975/76), no. 4, 281–306. MR 424589, DOI 10.1080/03081087608817121
Anthony V. Geramita and Jennifer Seberry Wallis, Orthogonal designs. III. Weighing matrices, Utilitas Math. 6 (1974), 209–236. MR 424592
Marc Gysin and Jennifer Seberry, On the weighing matrices of order $4n$ and weight $4n-2$ and $2n-1$, Australas. J. Combin. 12 (1995), 157–174. MR 1349207
Garrett Birkhoff and Morgan Ward, A characterization of Boolean algebras, Ann. of Math. (2) 40 (1939), 609–610. MR 9, DOI 10.2307/1968945
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
A.E. Ingham: The distribution of prime numbers. Cambridge Tract. No. 30. Cambridge University Press (1932).
Kenneth Ireland and Michael Rosen, A classical introduction to modern number theory, 2nd ed., Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York, 1990. MR 1070716, DOI 10.1007/978-1-4757-2103-4
Nathan Jacobson, Basic algebra. I, 2nd ed., W. H. Freeman and Company, New York, 1985. MR 780184
Dieter Jungnickel, On a theorem of Ganley, Graphs Combin. 3 (1987), no. 2, 141–143. MR 932130, DOI 10.1007/BF01788537
D. Jungnickel: Difference Sets. In: J.H. Dinitz and D.R. Stinson, eds., Contemporary Design Theory: A Collection of Surveys. Wiley, New York (1992), 241-324.
D. Jungnickel, B. Schmidt: Difference Sets: An Update. In: Geometry, Combinatorial Designs and Related Structures. Proceedings of the First Pythagorean Conference, Eds. J.W.P. Hirschfeld, S.S. Magliveras, M.J. de Resmini. Cambridge University Press (1997), 89-112.
Christos Koukouvinos and Jennifer Seberry, Weighing matrices and their applications, J. Statist. Plann. Inference 62 (1997), no. 1, 91–101. MR 1463380, DOI 10.1016/S0378-3758(96)00172-3
Eric S. Lander, Symmetric designs: an algebraic approach, London Mathematical Society Lecture Note Series, vol. 74, Cambridge University Press, Cambridge, 1983. MR 697566, DOI 10.1017/CBO9780511662164
Warwick de Launey, On the nonexistence of generalised weighing matrices, Ars Combin. 17 (1984), no. A, 117–132. MR 746179
S. L. Ma, Planar functions, relative difference sets, and character theory, J. Algebra 185 (1996), no. 2, 342–356. MR 1417375, DOI 10.1006/jabr.1996.0329
Saunders MacLane, Steinitz field towers for modular fields, Trans. Amer. Math. Soc. 46 (1939), 23–45. MR 17, DOI 10.1090/S0002-9947-1939-0000017-3
Henry B. Mann, Addition theorems: The addition theorems of group theory and number theory, Interscience Publishers John Wiley & Sons, New York-London-Sydney, 1965. MR 0181626
R.L. McFarland: On multipliers of abelian difference sets. Ph.D. Dissertation, Ohio State University (1970).
Robert L. McFarland, Difference sets in abelian groups of order $4p^2$, Mitt. Math. Sem. Giessen 192 (1989), i–iv, 1–70. MR 1010200
Robert L. McFarland, Sub-difference sets of Hadamard difference sets, J. Combin. Theory Ser. A 54 (1990), no. 1, 112–122. MR 1051782, DOI 10.1016/0097-3165(90)90009-L
Robert L. McFarland, Necessary conditions for Hadamard difference sets, Coding theory and design theory, Part II, IMA Vol. Math. Appl., vol. 21, Springer, New York, 1990, pp. 257–272. MR 1056539, DOI 10.1007/978-1-4615-6654-0_{1}8
R. C. Mullin, A note on balanced weighing matrices, Combinatorial mathematics, III (Proc. Third Australian Conf., Univ. Queensland, St. Lucia, 1974) Lecture Notes in Math., Vol. 452, Springer, Berlin, 1975, pp. 28–41. MR 0376397
R. G. Stanton and R. C. Mullin, On the nonexistence of a class of circulant balanced weighing matrices, SIAM J. Appl. Math. 30 (1976), no. 1, 98–102. MR 409234, DOI 10.1137/0130011
Hiroyuki Ohmori, Classification of weighing matrices of order $13$ and weight $9$, Discrete Math. 116 (1993), no. 1-3, 55–78. MR 1222119, DOI 10.1016/0012-365X(93)90394-9
Alexander Pott, Finite geometry and character theory, Lecture Notes in Mathematics, vol. 1601, Springer-Verlag, Berlin, 1995. MR 1440858, DOI 10.1007/BFb0094449
D. K. Ray-Chaudhuri and Qing Xiang, New necessary conditions for abelian Hadamard difference sets, J. Statist. Plann. Inference 62 (1997), no. 1, 69–79. MR 1463378, DOI 10.1016/S0378-3758(96)00170-X
Paulo Ribenboim, Algebraic numbers, Pure and Applied Mathematics, Vol. 27, Wiley-Interscience [A Division of John Wiley & Sons, Inc.], New York-London-Sydney, 1972. MR 0340212
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
Herbert John Ryser, Combinatorial mathematics, The Carus Mathematical Monographs, No. 14, Mathematical Association of America; distributed by John Wiley and Sons, Inc., New York, 1963. MR 0150048
B. Schmidt: Cyclotomic Integers of Prescribed Absolute Value and the Class Group, J. Number Theory 72 (1998), 269–281.
Jennifer Seberry Wallis and Albert Leon Whiteman, Some results on weighing matrices, Bull. Austral. Math. Soc. 12 (1975), no. 3, 433–447. MR 379238, DOI 10.1017/S0004972700024096
R. Turyn and J. Storer, On binary sequences, Proc. Amer. Math. Soc. 12 (1961), 394–399. MR 125026, DOI 10.1090/S0002-9939-1961-0125026-2
Richard J. Turyn, Character sums and difference sets, Pacific J. Math. 15 (1965), 319–346. MR 179098
R. Turyn, Sequences with small correlation, Error Correcting Codes (Proc. Sympos. Math. Res. Center, Madison, Wis., 1968), John Wiley, New York, 1968, pp. 195–228. MR 0242566
Q. Xiang: On reversible abelian Hadamard difference sets. J. Statist. Plann. Inference 73 (1998), 409–416.