Skip to main content
Log in

A survey of partial difference sets

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

LetG be a finite group of order ν. Ak-element subsetD ofG is called a (ν,k, λ, μ)-partial difference set if the expressionsgh −1, forg andh inD withgh, represent each nonidentity element inD exactly λ times and each nonidentity element not inD exactly μ times. IfeD andgD iffg −1D, thenD is essentially the same as a strongly regular Cayley graph. In this survey, we try to list all important existence and nonexistence results concerning partial difference sets. In particular, various construction methods are studied, e.g., constructions using partial congruence partitions, quadratic forms, cyclotomic classes and finite local rings. Also, the relations with Schur rings, two-weight codes, projective sets, difference sets, divisible difference sets and partial geometries are discussed in detail.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R.C. Bose. 1963. Strongly regular graphs, partial geometries and partially balanced designs.Pacific J. Math. 13: 389–419.

    Google Scholar 

  2. X.L. Hubaut. 1975. Strongly regular graphs.Discrete Math. 13: 357–381.

    Google Scholar 

  3. P.J. Cameron. 1978. Strongly regular graphs.Selected Topics in Graph Theory, (L.W. Beineke and R.J. Wilson, eds.). New York: Academic Press. pp. 337–360.

    Google Scholar 

  4. J.J. Seidel. 1979. Strongly regular graphs.Surveys in Combinatorics, (B. Bollabás, ed.). Cambridge: Cambridge University Press. pp. 157–180.

    Google Scholar 

  5. A.E. Brouwer and J.H. van Lint. 1984. Strongly rgular graphs and partial geometries.Enumeration and Designs, (D.M. Jackson and S.A. Vanstone, eds.). New York: Academic Press. pp. 85–122.

    Google Scholar 

  6. P.J. Cameron and J.H. van Lint. 1991.Designs, Graphs, Codes and Their Links. Cambridge: Cambridge University Press.

    Google Scholar 

  7. H.P. Yap. 1986.Some Topics in Graph Theory. Cambridge: Cambridge University Press.

    Google Scholar 

  8. I.M. Chakravarti. 1969. Partial difference sets, calibration designs and error correcting codes.Bull. Inter. Stat. Inst. 43(2): 104–106.

    Google Scholar 

  9. R.C. Bose and J.M. Cameron. 1965. The bridge tournament problem and calibration designs for comparing pairs of objects.Journal of Research of the NBS-B, Maths. and Math. Phys. 69: 323–332.

    Google Scholar 

  10. S.L. Ma. 1984. Partial difference sets.Discrete Math. 52: 75–89.

    Google Scholar 

  11. S.L. Ma. 1989. On association schemes, Schur rings, strongly regular graphs and partial difference sets.Ars. Combinatoria. 27: 211–220.

    Google Scholar 

  12. P. Delsarte. 1971. Two-weight linear codes and strongly regular graphs. Brussels: MBLE. Res. Lab. Report R160.

  13. P. Delsarte. 1972. Weights of linear codes and strongly regular normed spaces.Discrete Math. 3: 47–64.

    Google Scholar 

  14. P. Delsarte. 1973. An algebraic approach to the association schemes of coding theory.Philips Research Report. Suppl. No. 10.

  15. P. Camion. 1979.Difference Sets in Elementary Abelian Groups. Montreal: Les Presses de l'Université de Montréal.

    Google Scholar 

  16. W.G. Bridges and R.A. Mena. 1979. Rational spectra and cyclic strongly regular graphs.Ars Combinatoria. 8: 143–161.

    Google Scholar 

  17. W.G. Bridges and R.A. Mena. 1982. Rational G-matrices with rational eigenvalues.J. Combin. Theory Ser. A. 32: 264–280.

    Google Scholar 

  18. R. Calderbank and W.M. Kantor. 1986. The geometry of two-weight codes.Bull. London Math. Soc. 18: 97–122.

    Google Scholar 

  19. D. Ghinelli and S. Löwe. 1991. On multiplier of partial addition sets.Geometriae Dedicata. 40: 53–58.

    Google Scholar 

  20. T. Beth, D. Jungnickel, and H. Lenz. 1986.Design Theory. Cambridge: Cambridge University Press.

    Google Scholar 

  21. E.S. Lander. 1983.Symmetric Designs: An Algebraic Approach. Cambridge: Cambridge University Press.

    Google Scholar 

  22. D. Jungnickel. 1992. Difference sets.Contemporary Design Theory, (J.H. Dinitz and D.R. Stinson, eds.). New York: Wiley. pp. 241–324.

    Google Scholar 

  23. R.E.A.C. Paley. 1933. On orthogonal matrices.J. Math. Phys. 12: 311–320.

    Google Scholar 

  24. A.P. Sprague. 1982. Translation nets.Mitt. Math. Sem Giessen. 157: 46–68.

    Google Scholar 

  25. R.A. Bailey and D. Jungnickel. 1990. Translation nets and fixed-point-free group automorphisms.J. Combin. Theory Ser. A. 55: 1–13.

    Google Scholar 

  26. D. Jungnickel. 1990. Latin squares, their geometries and their groups. A survey.Coding Theory and Design Theory Part II: Design Theory, (D. Ray-Chaudhuri, ed.). New York: Springer-Verlag. pp. 166–225.

    Google Scholar 

  27. R.L. McFarland. 1973. A family of difference sets in non-cyclic groups.J. Combin. Theory Ser. A. 15: 1–10.

    Google Scholar 

  28. H.B. Mann. 1965.Addition Theorems. New York: Wiley.

    Google Scholar 

  29. O. Tamaschke. 1963. Zur Theorie der Permutationsgruppen mit regulärer Untergruppe.Math. Z. 80: 328–352.

    Google Scholar 

  30. D.R. Hughes, J.H. van Lint and R.M. Wilson. 1979. Announcement at the Seventh British Combinatorial Conference, Cambridge. Unpublished.

  31. I. Schur. 1933. Zur Theorie der enfach transitiven Permutationsgruppen.Sitz. Preuss. Akad. Wiss. Berlin. Phys-math. Kl. pp. 598–623.

  32. H. Wielandt. 1949. Zur Theorie der einfach transitiven Permutationsgruppen II.Math. Zeit. 52: 384–393.

    Google Scholar 

  33. H. Wielandt. 1964.Finite Permutation Groups. New York: Academic Press.

    Google Scholar 

  34. W. Scott. 1964.Group Theory. New Jersey: Prentice Hall.

    Google Scholar 

  35. R.C. Bose and D.M. Mesner. 1959. On linear association algebras corresponding to association schemes of partially balanced incomplete block designs,Ann. Math. Stat. 30: 21–38.

    Google Scholar 

  36. E. Bannai and T. Ito. 1984.Algebraic Combinatorics I: Association Schemes. Menlo Park: Benjamin/Cumming.

    Google Scholar 

  37. W. Scott. 1957. Solvable factorizable groups.Illinois J. Math. 1: 389–394.

    Google Scholar 

  38. S.L. Ma. 1987. Partial difference sets in dihedral groups.South East Asian Bull. Math. 11: 53–59.

    Google Scholar 

  39. M.J. de Resmini and D. Jungnickel. 1992. Strongly regular semi-Cayley graphs.J. Alg. Comb. 1: 171–195.

    Google Scholar 

  40. K.H. Leung and S.L. Ma. 1993. Partial difference triples.J. Alg. Comb. 2: 397–409.

    Google Scholar 

  41. S.L. Ma. 1985.Polynomial Addition Sets. University of Hong Kong. Thesis.

  42. S.L. Ma. 1990. Polynomial addition sets and symmetric difference sets.Coding Theory and Design Theory Part II: Design Theory, (D. Ray-Chaudhuri, ed.). New York: Springer-Verlag. pp. 273–279.

    Google Scholar 

  43. J.A. Davis, Preprint. Partial difference sets in p-groups.

  44. S.L. Ma. 1994. On subsets of partial difference sets.Discrete Math.

  45. F.J. MacWilliams and N.J.A. Sloane. 1977.The Theory of Error-Correcting Codes. Amsterdam: North-Holland.

    Google Scholar 

  46. J.H. van Lint. 1982.Introduction to Coding Theory. New York: Springer-Verlag.

    Google Scholar 

  47. V. Pless. 1989.The Theory of Error-Correcting Codes. Second Edition. New York: Wiley.

    Google Scholar 

  48. F.J. MacWilliams. 1962.Combinatorial Problems in Elementary Abelian Groups. Harvard University. Thesis.

  49. F.J. MacWilliams. 1963. A thoerem on the distribution of weights in a systematic code.Bell System Tech. J. 42: 79–94.

    Google Scholar 

  50. M.J.E. Golay. 1949. Notes on digital coding.Proc. IRE. 37: 657.

    Google Scholar 

  51. A. Tietäväinen. 1974. A short proof for the non-existence of unknown perfect codes over GF(q), q>2.Ann. Acad. Sci. Fenn. Ser. A I. Math. 580: 1–6.

    Google Scholar 

  52. J.H. van Lint. 1975. A survey of perfect codes.Rocky Mountain J. Math. 5: 199–224.

    Google Scholar 

  53. N.V. Semakov, V.A. Zinovjev and G.V. Zaitzev. 1971. Uniformly packed codes.Problems Inform. Transmission. 7 (no. 1): 30–39.

    Google Scholar 

  54. J.M. Goethals and H.C.A. van Tilborg. 1975. Uniformly packed codes.Philips Research Reports. 30: 9–36.

    Google Scholar 

  55. H.C.A. van Tilborg. 1976.Uniformly Packed Codes. Tech. Univ. Eindhoven. Thesis.

  56. R. Calderbank. 1982. On uniformly packed [n, n-k, 4] codes over GF(q) and a class of caps in PG(k-1, q).J. London Math. Soc. 26: 365–384.

    Google Scholar 

  57. J.W.P. Hirschfeld. 1979.Projective Geometries Over Finite Fields. Oxford: Oxford University Press.

    Google Scholar 

  58. P. Dembowski. 1968.Finite Geometries. New York: Springer-Verlag.

    Google Scholar 

  59. L.E. Denniston. 1969. Some maximal arcs in finite projective planes.J. Combin. Theory. 6: 317–319.

    Google Scholar 

  60. A.E. Brouwer. 1985. Some new two-weight codes and strongly regular graphs.Discrete Applied Math. 10: 111–114.

    Google Scholar 

  61. M.J. de Resmini. 1983. An infinite family of type (m, n) sets in PG(2, q2), q a square.J. Geom. 20: 36–43.

    Google Scholar 

  62. M.J. de Resmini. 1987. A 35-set of type (2, 5) in PG(2, 9).J. Combin. Theory Ser. A. 45: 303–305.

    Google Scholar 

  63. M.J. de Resmini and G. Migliori. 1986. A 78-set of type (2, 6) in PG(2, 16).Ars Combinatoria. 22: 73–75.

    Google Scholar 

  64. B. Segre. 1965. Forme e geometrie hermitiane, con particolare riguardo al caso finito.Ann. Mat. Pura Appl. 70: 1–202.

    Google Scholar 

  65. R. Hill. 1973. On the largest size cap in S5,3.Rend. Accad. Naz. Lincei (8). 54: 378–384.

    Google Scholar 

  66. N. Tzanakis and J. Wolfskill. 1987. The diophantine equation x2=4qa/2+4q+1 with an application to coding theory.J. Number Theory. 26: 96–116.

    Google Scholar 

  67. J.A. Thas. 1973. A combinatorial problem.Geometriae Dedicata. 1: 236–240.

    Google Scholar 

  68. J. Storer. 1967.Cyclotomy and Difference Sets. Chicago: Markham.

    Google Scholar 

  69. L.D. Baumert, W.H. Mills, and R.L. Ward. 1982. Uniformly cyclotomy.J. Number Theory. 14: 67–82.

    Google Scholar 

  70. J.H. van Lint and A. Schrijver. 1981. Construction of strongly regular graphs, two-weight codes and partial geometries by finite fields.Combinatorica. 1: 63–73.

    Google Scholar 

  71. R. Hill. 1976. Caps and groups.Atti dei Convegni Lincei, Colloquio Internazionale sulle Teorie Combinatorie (Roma 1973), no. 7. Accad. Naz. Lincei. pp. 384–394.

  72. C.L.M. de Lange. 1990.Cyclotomic Graphs. Tech. Univ. Eindhoven. Thesis.

  73. K.H. Leung and S.L. Ma. 1990. Constructions of partial difference sets and relative difference sets on p-group.Bull. London Math. Soc. 22: 533–539.

    Google Scholar 

  74. J.F. Dillon. 1987. Difference sets in 2-groups.Proc. NSA Math. Sci. Meeting. pp. 165–172.

  75. E.C. Johnsen. 1964. The inverse multiplier for abelian group difference sets.Can. J. Math. 16: 787–796.

    Google Scholar 

  76. D. Ghinelli. 1987. A new result on difference sets with −1 as multiplier.Geometriae Dedicata. 23: 309–317.

    Google Scholar 

  77. D. Jungnickel. 1982. Difference sets with multiplier −1.Arch. Math. 38: 511–513.

    Google Scholar 

  78. R.L. McFarland and S.L. Ma. 1990. Abelian difference sets with multiplier minus one.Arch. Math. 54: 610–623.

    Google Scholar 

  79. R.L. McFarland. 1990. Sub-difference sets of Hadamard difference sets.J. Combin. Theory Ser. A. 54: 112–122.

    Google Scholar 

  80. S.L. Ma. 1992. McFarland's conjecture on abelian difference sets with multiplier −1.Designs, Codes and Cryptography. 1: 321–332.

    Google Scholar 

  81. M. Xia. 1992. Some infinite classes of special Williamson matrices and difference sets.J. Combin. Theory Ser. A. 61: 230–242.

    Google Scholar 

  82. P.K. Menon. 1962. On difference sets whose parameters satisfy a certain relation.Proc. Amer. Math. Soc. 13: 739–745.

    Google Scholar 

  83. R.J. Turyn. 1984. A special class of Williamson matrices and difference sets.J. Combin. Theory Ser. A. 36: 111–115.

    Google Scholar 

  84. K.T. Arasu. 1990. Recent results on difference sets.Coding Theory and Design Theory Part II: Design Theory, (Ray-Chaudhuri, D. ed.). New York: Springer-Verlag, pp. 1–23.

    Google Scholar 

  85. H.B. Mann. 1965. Difference sets in elementary abelian groups.Ill. J. Math. 17: 541–542.

    Google Scholar 

  86. K.W. Smith. Preprint. Non-abelian Hadamard difference sets.

  87. M. Miyamoto. 1983. A family of difference sets having −1 as an invariant.Hokkaido Math. J. 12: 24–26.

    Google Scholar 

  88. S.L. Ma. 1989. A family of difference sets having −1 as an invariant.Europ. J. Combinatorics 10: 273–274.

    Google Scholar 

  89. D. Ghinelli. 1992. Regular groups on generalized quadrangles and nonabelian difference sets with multiplier −1.Geometriae Dedicata. 41:165–174.

    Google Scholar 

  90. K.T. Arasu, D. Jungnickel, S.L. Ma, and A. Pott. To appear. Strongly regular Cayley graphs with λ-μ=−1.J. Combin. Theory Ser. A.

  91. D. Jungnickel. 1982. On automorphism groups of divisible designs.Canad. J. Math. 34: 257–297.

    Google Scholar 

  92. K.T. Arasu, D. Jungnickel, and A. Pott. 1990. Divisible difference sets with multiplier-1.J. Algebra 133: 35–62.

    Google Scholar 

  93. K.T. Arasu, D. Jungnickel, and A. Pott. 1991. Symmetric divisible designs withk-λ 1-1.Discrete Math. 97: 25–38.

    Google Scholar 

  94. K.H. Leung and S.L. Ma. Preprint. Partial difference sets with Paley parameters.

  95. J.A. Thas. 1977. Combinatorics of partial geometries and generalized quadrangles.Higher Combinatorics, (M. Aigner, ed.). Dordrecht: Reidel. pp. 183–199.

    Google Scholar 

  96. L.D. Baumert. 1971.Cyclic Difference Sets. New York: Springer-Verlag.

    Google Scholar 

  97. S.L. Ma. Preprint. Regular automorphism groups on partial geometries.

  98. S.E. Payne and J.A. Thas. 1984.Finite Generalized Quadrangles. Boston: Pitman.

    Google Scholar 

  99. S. Löwe. Preprint. Constructions of GQs.

  100. A.E. Brouwer and A. Neumaier. 1981. Strongly regular graphs where μ=2 and λ is large. Amsterdam: Math. Centrum. Report 151/81.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Additional information

Communicated by D. Jungnickel

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ma, S.L. A survey of partial difference sets. Des Codes Crypt 4, 221–261 (1994). https://doi.org/10.1007/BF01388454

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01388454

Keywords

Navigation