Cyclotomic integers and finite geometry
HTML articles powered by AMS MathViewer
- by Bernhard Schmidt PDF
- J. Amer. Math. Soc. 12 (1999), 929-952 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.
Additional Information
- Bernhard Schmidt
- Affiliation: Department of Mathematics, 253-37 Caltech, Pasadena, California 91125
- Address at time of publication: Am alten Hof 12, 63683 Ortenberg, Germany
- Email: schmidt@cco.caltech.edu
- Received by editor(s): March 2, 1998
- Received by editor(s) in revised form: May 8, 1998
- Published electronically: May 5, 1999
- © Copyright 1999 American Mathematical Society
- Journal: J. Amer. Math. Soc. 12 (1999), 929-952
- MSC (1991): Primary 05B10; Secondary 05B20
- DOI: https://doi.org/10.1090/S0894-0347-99-00298-2
- MathSciNet review: 1671453