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 withg≠h, represent each nonidentity element inD exactly λ times and each nonidentity element not inD exactly μ times. Ife∉D andg∈D iffg −1∈D, 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R.C. Bose. 1963. Strongly regular graphs, partial geometries and partially balanced designs.Pacific J. Math. 13: 389–419.
X.L. Hubaut. 1975. Strongly regular graphs.Discrete Math. 13: 357–381.
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.
J.J. Seidel. 1979. Strongly regular graphs.Surveys in Combinatorics, (B. Bollabás, ed.). Cambridge: Cambridge University Press. pp. 157–180.
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.
P.J. Cameron and J.H. van Lint. 1991.Designs, Graphs, Codes and Their Links. Cambridge: Cambridge University Press.
H.P. Yap. 1986.Some Topics in Graph Theory. Cambridge: Cambridge University Press.
I.M. Chakravarti. 1969. Partial difference sets, calibration designs and error correcting codes.Bull. Inter. Stat. Inst. 43(2): 104–106.
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.
S.L. Ma. 1984. Partial difference sets.Discrete Math. 52: 75–89.
S.L. Ma. 1989. On association schemes, Schur rings, strongly regular graphs and partial difference sets.Ars. Combinatoria. 27: 211–220.
P. Delsarte. 1971. Two-weight linear codes and strongly regular graphs. Brussels: MBLE. Res. Lab. Report R160.
P. Delsarte. 1972. Weights of linear codes and strongly regular normed spaces.Discrete Math. 3: 47–64.
P. Delsarte. 1973. An algebraic approach to the association schemes of coding theory.Philips Research Report. Suppl. No. 10.
P. Camion. 1979.Difference Sets in Elementary Abelian Groups. Montreal: Les Presses de l'Université de Montréal.
W.G. Bridges and R.A. Mena. 1979. Rational spectra and cyclic strongly regular graphs.Ars Combinatoria. 8: 143–161.
W.G. Bridges and R.A. Mena. 1982. Rational G-matrices with rational eigenvalues.J. Combin. Theory Ser. A. 32: 264–280.
R. Calderbank and W.M. Kantor. 1986. The geometry of two-weight codes.Bull. London Math. Soc. 18: 97–122.
D. Ghinelli and S. Löwe. 1991. On multiplier of partial addition sets.Geometriae Dedicata. 40: 53–58.
T. Beth, D. Jungnickel, and H. Lenz. 1986.Design Theory. Cambridge: Cambridge University Press.
E.S. Lander. 1983.Symmetric Designs: An Algebraic Approach. Cambridge: Cambridge University Press.
D. Jungnickel. 1992. Difference sets.Contemporary Design Theory, (J.H. Dinitz and D.R. Stinson, eds.). New York: Wiley. pp. 241–324.
R.E.A.C. Paley. 1933. On orthogonal matrices.J. Math. Phys. 12: 311–320.
A.P. Sprague. 1982. Translation nets.Mitt. Math. Sem Giessen. 157: 46–68.
R.A. Bailey and D. Jungnickel. 1990. Translation nets and fixed-point-free group automorphisms.J. Combin. Theory Ser. A. 55: 1–13.
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.
R.L. McFarland. 1973. A family of difference sets in non-cyclic groups.J. Combin. Theory Ser. A. 15: 1–10.
H.B. Mann. 1965.Addition Theorems. New York: Wiley.
O. Tamaschke. 1963. Zur Theorie der Permutationsgruppen mit regulärer Untergruppe.Math. Z. 80: 328–352.
D.R. Hughes, J.H. van Lint and R.M. Wilson. 1979. Announcement at the Seventh British Combinatorial Conference, Cambridge. Unpublished.
I. Schur. 1933. Zur Theorie der enfach transitiven Permutationsgruppen.Sitz. Preuss. Akad. Wiss. Berlin. Phys-math. Kl. pp. 598–623.
H. Wielandt. 1949. Zur Theorie der einfach transitiven Permutationsgruppen II.Math. Zeit. 52: 384–393.
H. Wielandt. 1964.Finite Permutation Groups. New York: Academic Press.
W. Scott. 1964.Group Theory. New Jersey: Prentice Hall.
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.
E. Bannai and T. Ito. 1984.Algebraic Combinatorics I: Association Schemes. Menlo Park: Benjamin/Cumming.
W. Scott. 1957. Solvable factorizable groups.Illinois J. Math. 1: 389–394.
S.L. Ma. 1987. Partial difference sets in dihedral groups.South East Asian Bull. Math. 11: 53–59.
M.J. de Resmini and D. Jungnickel. 1992. Strongly regular semi-Cayley graphs.J. Alg. Comb. 1: 171–195.
K.H. Leung and S.L. Ma. 1993. Partial difference triples.J. Alg. Comb. 2: 397–409.
S.L. Ma. 1985.Polynomial Addition Sets. University of Hong Kong. Thesis.
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.
J.A. Davis, Preprint. Partial difference sets in p-groups.
S.L. Ma. 1994. On subsets of partial difference sets.Discrete Math.
F.J. MacWilliams and N.J.A. Sloane. 1977.The Theory of Error-Correcting Codes. Amsterdam: North-Holland.
J.H. van Lint. 1982.Introduction to Coding Theory. New York: Springer-Verlag.
V. Pless. 1989.The Theory of Error-Correcting Codes. Second Edition. New York: Wiley.
F.J. MacWilliams. 1962.Combinatorial Problems in Elementary Abelian Groups. Harvard University. Thesis.
F.J. MacWilliams. 1963. A thoerem on the distribution of weights in a systematic code.Bell System Tech. J. 42: 79–94.
M.J.E. Golay. 1949. Notes on digital coding.Proc. IRE. 37: 657.
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.
J.H. van Lint. 1975. A survey of perfect codes.Rocky Mountain J. Math. 5: 199–224.
N.V. Semakov, V.A. Zinovjev and G.V. Zaitzev. 1971. Uniformly packed codes.Problems Inform. Transmission. 7 (no. 1): 30–39.
J.M. Goethals and H.C.A. van Tilborg. 1975. Uniformly packed codes.Philips Research Reports. 30: 9–36.
H.C.A. van Tilborg. 1976.Uniformly Packed Codes. Tech. Univ. Eindhoven. Thesis.
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.
J.W.P. Hirschfeld. 1979.Projective Geometries Over Finite Fields. Oxford: Oxford University Press.
P. Dembowski. 1968.Finite Geometries. New York: Springer-Verlag.
L.E. Denniston. 1969. Some maximal arcs in finite projective planes.J. Combin. Theory. 6: 317–319.
A.E. Brouwer. 1985. Some new two-weight codes and strongly regular graphs.Discrete Applied Math. 10: 111–114.
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.
M.J. de Resmini. 1987. A 35-set of type (2, 5) in PG(2, 9).J. Combin. Theory Ser. A. 45: 303–305.
M.J. de Resmini and G. Migliori. 1986. A 78-set of type (2, 6) in PG(2, 16).Ars Combinatoria. 22: 73–75.
B. Segre. 1965. Forme e geometrie hermitiane, con particolare riguardo al caso finito.Ann. Mat. Pura Appl. 70: 1–202.
R. Hill. 1973. On the largest size cap in S5,3.Rend. Accad. Naz. Lincei (8). 54: 378–384.
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.
J.A. Thas. 1973. A combinatorial problem.Geometriae Dedicata. 1: 236–240.
J. Storer. 1967.Cyclotomy and Difference Sets. Chicago: Markham.
L.D. Baumert, W.H. Mills, and R.L. Ward. 1982. Uniformly cyclotomy.J. Number Theory. 14: 67–82.
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.
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.
C.L.M. de Lange. 1990.Cyclotomic Graphs. Tech. Univ. Eindhoven. Thesis.
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.
J.F. Dillon. 1987. Difference sets in 2-groups.Proc. NSA Math. Sci. Meeting. pp. 165–172.
E.C. Johnsen. 1964. The inverse multiplier for abelian group difference sets.Can. J. Math. 16: 787–796.
D. Ghinelli. 1987. A new result on difference sets with −1 as multiplier.Geometriae Dedicata. 23: 309–317.
D. Jungnickel. 1982. Difference sets with multiplier −1.Arch. Math. 38: 511–513.
R.L. McFarland and S.L. Ma. 1990. Abelian difference sets with multiplier minus one.Arch. Math. 54: 610–623.
R.L. McFarland. 1990. Sub-difference sets of Hadamard difference sets.J. Combin. Theory Ser. A. 54: 112–122.
S.L. Ma. 1992. McFarland's conjecture on abelian difference sets with multiplier −1.Designs, Codes and Cryptography. 1: 321–332.
M. Xia. 1992. Some infinite classes of special Williamson matrices and difference sets.J. Combin. Theory Ser. A. 61: 230–242.
P.K. Menon. 1962. On difference sets whose parameters satisfy a certain relation.Proc. Amer. Math. Soc. 13: 739–745.
R.J. Turyn. 1984. A special class of Williamson matrices and difference sets.J. Combin. Theory Ser. A. 36: 111–115.
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.
H.B. Mann. 1965. Difference sets in elementary abelian groups.Ill. J. Math. 17: 541–542.
K.W. Smith. Preprint. Non-abelian Hadamard difference sets.
M. Miyamoto. 1983. A family of difference sets having −1 as an invariant.Hokkaido Math. J. 12: 24–26.
S.L. Ma. 1989. A family of difference sets having −1 as an invariant.Europ. J. Combinatorics 10: 273–274.
D. Ghinelli. 1992. Regular groups on generalized quadrangles and nonabelian difference sets with multiplier −1.Geometriae Dedicata. 41:165–174.
K.T. Arasu, D. Jungnickel, S.L. Ma, and A. Pott. To appear. Strongly regular Cayley graphs with λ-μ=−1.J. Combin. Theory Ser. A.
D. Jungnickel. 1982. On automorphism groups of divisible designs.Canad. J. Math. 34: 257–297.
K.T. Arasu, D. Jungnickel, and A. Pott. 1990. Divisible difference sets with multiplier-1.J. Algebra 133: 35–62.
K.T. Arasu, D. Jungnickel, and A. Pott. 1991. Symmetric divisible designs withk-λ 1-1.Discrete Math. 97: 25–38.
K.H. Leung and S.L. Ma. Preprint. Partial difference sets with Paley parameters.
J.A. Thas. 1977. Combinatorics of partial geometries and generalized quadrangles.Higher Combinatorics, (M. Aigner, ed.). Dordrecht: Reidel. pp. 183–199.
L.D. Baumert. 1971.Cyclic Difference Sets. New York: Springer-Verlag.
S.L. Ma. Preprint. Regular automorphism groups on partial geometries.
S.E. Payne and J.A. Thas. 1984.Finite Generalized Quadrangles. Boston: Pitman.
S. Löwe. Preprint. Constructions of GQs.
A.E. Brouwer and A. Neumaier. 1981. Strongly regular graphs where μ=2 and λ is large. Amsterdam: Math. Centrum. Report 151/81.
Author information
Authors and Affiliations
Additional information
Communicated by D. Jungnickel
Rights 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
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01388454