×

zbMATH — the first resource for mathematics

New cyclic difference sets with Singer parameters. (English) Zbl 1043.05024
Summary: The main result in this paper is a general construction of \(\phi(m)/2\) pairwise inequivalent cyclic difference sets with Singer parameters \((v,k,\lambda)= (2^m-1, 2^{m-1}, 2^{m-2})\) for any \(m \geqslant 3\). The construction was conjectured by the second author at Oberwolfach in 1998. We also give a complete proof of related conjectures made by J.-S. No, H. Chung and M.-S. Yun [IEEE Trans. Inf. Theory 44, 1278–1282 (1998; Zbl 0912.94017)] and by J.-S. No, L. W. Golomb, G. Gong, H.-K. Lee and G. Gaal [ibid., 814–817 (1998; Zbl 0912.94016)] which produce another difference set for each \(m\geqslant 7\) not a multiple of 3. Our proofs exploit Fourier analysis on the additive group of GF(\(2^m\)) and draw heavily on the theory of quadratic forms in characteristic 2. By-products of our results are a new class of bent functions and a new short proof of the exceptionality of the Müller–Cohen–Matthews polynomials. Furthermore, following the results of this paper, there are today no sporadic examples of difference sets with these parameters; i.e. every known such difference set belongs to a series given by a constructive theorem.

MSC:
05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.)
11T06 Polynomials over finite fields
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Artin, E, Geometric algebra, (1957), Interscience New York
[2] Assmus, E.F; Key, J.D, Designs and their codes, Cambridge tracts in mathematics, Vol. 103, (1992), Cambridge University Press Cambridge · Zbl 0762.05001
[3] Baumert, L.D, Cyclic difference sets, Lecture notes in mathematics, Vol. 182, (1971), Springer Berlin, Heidelberg, New York · Zbl 0218.05009
[4] Beth, T; Jungnickel, D; Lenz, H, Design theory, (1999), Cambridge University Press Cambridge
[5] Berndt, B.C; Evans, R.J; Williams, K.S, Gauss and Jacobi sums, (1988), Wiley New York
[6] Biggs, N.L; Kirkman, T.P, Mathematician, Bull. London math. soc., 13, 97-120, (1981) · Zbl 0454.01015
[7] A. Chang, P. Gaal, S.W. Golomb, G. Gong, P.V. Kumar, Some results relating to sequences conjectured to have ideal autocorrelation, preprint.
[8] A. Chang, T. Helleseth, P.V. Kumar, Further results on a conjectured 2-level autocorrelation sequence, preprint.
[9] Cohen, S.D; Matthews, R.W, A class of exceptional polynomials, Trans. amer. math. soc., 345, 897-909, (1994) · Zbl 0812.11070
[10] Coulter, R.S, The number of rational points of a class of artin – schreier curves, Finite fields appl., 8, 397-413, (2002) · Zbl 1056.11038
[11] Dieudonné, J, La Géométrie des groupes classiques, (1963), Springer Berlin, Göttingen, Heidelberg · Zbl 0111.03102
[12] Dillon, J.F, Multiplicative difference sets via additive characters, Des. codes cryptogr., 17, 225-235, (1999) · Zbl 0944.05012
[13] Dickson, L.E, Linear groups, (1958), Dover New York
[14] Dobbertin, H, Almost perfect nonlinear power functions on GF(2^{n})the welch case, IEEE trans. inform. theory, 45, 1271-1275, (1999) · Zbl 0957.94021
[15] Dobbertin, H, Almost perfect nonlinear power functions on GF(2^{n})the niho case, Inform. comput., 151, 57-72, (1999) · Zbl 1072.94513
[16] Dobbertin, H, Another proof of Kasami’s theorem, Des. codes cryptogr., 17, 177-180, (1999) · Zbl 0941.94013
[17] H. Dobbertin, Kasami power functions, permutation polynomials and cyclic difference sets, in: A. Pott, P.V. Kumar, T. Helleseth, D. Jungnickel (Eds.), Difference Sets, Sequences and their Correlation Properties, Proceedings of the NATO Advanced Study Institute on Difference Sets, Sequences and their Correlation Properties, Bad Windsheim, 2-14 August 1998, Kluwer, Dordrecht, 1999, pp. 133-158.
[18] H. Dobbertin, Uniformly representable permutation polynomials, in: T. Helleseth, P.V. Kumar, K. Yang (Eds.), Sequences and their applications—SETA 01, Proceedings of SETA ’01, Springer, London, 2002, pp. 1-22. · Zbl 1041.11081
[19] Glynn, D, Two new sequences of ovals in finite Desarguesian planes of even order, (), 217-229
[20] Gold, R, Maximal recursive sequences with 3-valued cross-correlation functions, IEEE trans. inform. theory, 14, 154-156, (1968) · Zbl 0228.62040
[21] Golomb, S.W, Shift register sequences, (1967), Holden-Day San Francisco
[22] G. Gong, P. Gaal, S.W. Golomb, A suspected new infinite class of (2^{n}−1, 2n−1−1, 2n−2−1) cyclic difference sets, ITW, Longyearbyen, Norway, 6-12 July 1997, preprint.
[23] Gong, G; Golomb, S.W, Hadamard transforms of three-term sequences, IEEE trans. inform. theory, 45, 2059-2060, (1999) · Zbl 0958.94019
[24] Gordon, B; Mills, W.H; Welch, L.R, Some new difference sets, Canad. J. math., 14, 614-625, (1962) · Zbl 0111.24201
[25] Hall, M, A survey of difference sets, Proc. amer. math. soc., 7, 975-986, (1956) · Zbl 0077.05202
[26] Hall, M, Combinatorial theory, (1986), Wiley New York
[27] Hamada, N; Ohmori, H, On the BIB-design having the minimum p-rank, J. combin. theory A, 18, 131-140, (1975) · Zbl 0308.05012
[28] Jacobson, N, Basic algebra II, (1989), Freeman New York
[29] Kasami, T, The weight enumerators for several classes of subcodes of the second order binary reed – muller codes, Information and control, 18, 369-394, (1971) · Zbl 0217.58802
[30] Kirkman, T.P, On the perfect r-partitions of r2−r+1, Trans. hist. soc. lancashire Cheshire, 9, 127-142, (1856-7)
[31] R. Lidl, G.L. Mullen, G. Turnwald, Dickson Polynomials, Pitman Monographs in Pure and Applied Mathematics, Vol. 65, Addison-Wesley, Reading, MA, 1993.
[32] MacWilliams, F.J; Sloane, N.J.A, The theory of error-correcting codes, (1978), North-Holland New York
[33] Maschietti, A, Difference sets and hyperovals, Des. codes cryptogr., 14, 89-98, (1998) · Zbl 0887.05010
[34] P. Müller, New examples of exceptional polynomials, in: G.L. Mullen, P.J. Shiue (Eds.), Finite Fields: Theory, Applications and Algorithms; Contemp. Math. 168 (1994) 245-249.
[35] No, J.-S; Chung, H; Yun, M.-S, Binary pseudorandom sequences of period 2^{m}−1 with ideal autocorrelation generated by the polynomial zd+(z+1)d, IEEE trans. inform. theory, 44, 1278-1282, (1998) · Zbl 0912.94017
[36] No, J.-S; Golomb, S.W; Gong, G; Lee, H.-K; Gaal, P, Binary pseudorandom sequences of period 2^{m}−1 with ideal autocorrelation, IEEE trans. inform. theory, 44, 814-817, (1998) · Zbl 0912.94016
[37] Paley, R.E.A.C, On orthogonal matrices, J. math. phys., 12, 311-320, (1933) · JFM 59.0114.04
[38] Rothaus, O.S, On bent functions, J. combin. theory A, 20, 300-305, (1976) · Zbl 0336.12012
[39] Scarpis, U, Sui determinanti di valore massimo, Rend. reale istit. lombardo sci. lett. (milano rend.), 31, 1441-1446, (1898)
[40] Scholtz, R.A; Welch, L.R, GMW sequences, IEEE trans. inform. theory, 30, 548-553, (1984) · Zbl 0544.65005
[41] M.K. Simon, J. Omura, R. Scholtz, K. Levitt, Spread Spectrum Communications, Vols. I-III, Computer Science Press, Rockville, 1985.
[42] Singer, J, A theorem in finite projective geometry and some applications to number theory, Trans. amer. math. soc., 43, 377-385, (1938) · JFM 64.0972.04
[43] Q. Xiang, Recent results on difference sets with classical parameters, in: A. Pott, P.V. Kumar, T. Helleseth, D. Jungnickel (Eds.), Difference Sets, Sequences and their Correlation Properties, Proceedings of the NATO Advanced Study Institute on Difference Sets, Sequences and their Correlation Properties, Bad Windsheim, 2-14 August 1998, Kluwer, Dordrecht, 1999, pp. 419-437.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.