login
A333852
Irregular triangle read by rows: representative simple difference sets of Singer type of order m, for m = A000961(n), for n >= 1.
9
0, 1, 0, 1, 3, 0, 1, 5, 0, 1, 3, 9, 0, 1, 4, 6, 0, 1, 5, 11, 0, 1, 8, 10, 0, 1, 4, 14, 16, 0, 1, 6, 8, 18, 0, 1, 3, 8, 12, 18, 0, 1, 3, 10, 14, 26, 0, 1, 4, 6, 13, 21, 0, 1, 4, 10, 12, 17, 0, 1, 6, 18, 22, 29, 0, 1, 8, 11, 13, 17, 0, 1, 11, 19, 26, 28, 0, 1, 14, 20, 24, 29, 0, 1, 15, 19, 21, 24, 0, 1, 15, 20, 22, 28
OFFSET
1,5
COMMENTS
The length of row n is (A000961(n) + 1)*A335866(n) = {2, 6, 16, 10, 60, 96, ...}. Every representative difference set begins with 0, 1, ... .
A simple difference set of Singer type of order m in the additive group (Z_v(m),+), with complete residue system modulo v(m) chosen as RS(v(m)) = {0, 1, ..., v(m)-1}, where v(m) := m^2 + m + 1, is denoted by (v(m), m+1, 1), provided m = m(n) = A000961(n) (powers of primes), for n >= 1. It is defined by a set of m+1 integers {a_0, a_1, ..., a_m}, with a_j from RS(v(m)) such that the m*(m+1) differences d_{i, j} := a_i - a_j (mod v(m)), with i not j, give (in some order) the nonzero members of RS(v(m)) i.e., {1,2, ..., (m+1)*m} exactly once. (v is a notation used in block designs, originating from 'variety'; see the Stinson reference, p. 2.)
A representative difference set of this type is one which uses 0 and 1 as elements. By adding each element of a given representative difference set by 1, 2, ..., (m+1)*m, modulo m^2 + m + 1, all m^2 + m + 1 members of a class of difference sets are obtained. This equivalence class is called Dev(D), the development of a difference set $D$. The number of representative difference sets, hence the number of classes, has been conjectured by Singer, and is given in A335866(n). The difference sets will here be ordered increasingly. The set of all A335866(n) representative difference sets of this type will here be denoted by Sr(m) (also increasingly ordered). See the W. Lang link for these representatives of order m = m(n) = A000961(n), for n = 1, 2, ..., 11. The set of all difference sets of order m will be denoted by S(m).
A symmetric BIBD (Balanced Incomplete Block Design) is a block design (X, A) (X a set of points, A a set of nonempty subsets of A, called blocks), denoted by (v, k, lambda) with v = |A|, k = |B_i|, v > k >= 2, for each block B_i from A, and each pair of distinct points of X appears exactly in lambda blocks. The number of appearances of each point of X (the replication number) is r = lambda*(v-1)/(k-1), and the number of blocks is b = v*r/k. For symmetric BIBDs v = b. See, e.g., the Stinson reference, p. 2 and pp. 41 - 58.
A symmetric and simple (lambda = 1) BIBD (symsBIBD) (m^2+m+1, m+1, 1), with k = r = m+1 and b = v = m*(m+1) + 1, is called a projective plane of order m, if m >= 2. The trivial case (3, 2, 1) for m = 1 (a triangle) is not regarded as a projective plane. m = 2 gives the Fano plane (7, 3, 1). See Stinson, p. 27, and the links. Not all m values allow such a symsBIBD. Singer proved that for m a power of a prime (including 1) such symsBIBD exist.
See the Singer reference, Theorem, pp. 380-381, where this is called a perfect difference set of order m + 1 (not m like here, and in Stinson). There only one representative is given for allowed m values. The other ones can be obtained by using certain multipliers M from the restricted residue system RRS(v = m^2+m+1), and omitting powers of divisors of m, applied to each entry, taken modulo v(m). There are A335866(n) - 1 other representative difference sets. For more details see Stinson, sect. 3.4., pp. 54-58. In the W. Lang link all representative difference sets for m = 1, 2, 3, 4, 5, 7, 8, 9, 11, 13 and 16 are given, with explanations on how to find them using Stinson's approach.
A general card game Dobble (see the Goertz link) can use v = m*(m+1) + 1 cards with k = m+1 distinct symbols from a repertoire of v distinct symbols, where m is a power of a prime. The task is to find out the one common symbol of any pair of cards. E.g., m = 7, v = 57, k = 8. One can compose 12 = A335866(6) possible such 57 card decks with different distributions of the 8 from 57 symbols.
REFERENCES
Douglas R. Stinson, Combinatorial Designs, Springer, 2004.
LINKS
Ralf Goertz, Differenzmengen, Kartenspiel-Algebra, Spektrum Spezial, Physik Mathematik Technik, 4.18 (2018), pp. 24-29 (in German).
James Singer, A Theorem in Finite Projective Geometry and Some Applications to Number Theory, Trans. AMS, 43 (1938) 377-385, Table on p. 384.
Eric Weisstein's World of Mathematics, Difference Set
Wikipedia, Difference set.
EXAMPLE
The irregular triangle T(n, k) begins (0 1 3 stands for the set {0, 1, 3}, etc., and a vertical bar separates the sets):
n, m \ k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...
--------------------------------------------------------
1, 1: 0 1
2, 2: 0 1 3| 0 1 5
3, 3: 0 1 3 9| 0 1 4 6|0 1 5 11| 0 1 8 10
4, 4: 0 1 4 14 16|0 1 6 8 18
...
--------------------------------------------------------
n = 5, m = 5: {0, 1, 3, 8, 12, 18}, {0, 1, 3, 10, 14, 26}, {0, 1, 4, 6, 13, 21}, {0, 1, 4, 10, 12, 17}, {0, 1, 6, 18, 22, 29}, {0, 1, 8, 11, 13, 17}, {0, 1, 11, 19, 26, 28}, {0, 1, 14, 20, 24, 29}, {0, 1, 15, 19, 21, 24}, {0, 1, 15, 20, 22, 28};
n = 6, m = 7: {0, 1, 3, 13, 32, 36, 43, 52}, {0, 1, 4, 9, 20, 22, 34, 51}, {0, 1, 4, 12, 14, 30, 37, 52}, {0, 1, 5, 7, 17, 35, 38, 49}, {0, 1, 5, 27, 34, 37, 43, 45}, {0, 1, 6, 15, 22, 26, 45, 55}, {0, 1, 6, 21, 28, 44, 46, 54}, {0, 1, 7, 19, 23, 44, 47, 49}, {0, 1, 7, 24, 36, 38, 49, 54}, {0, 1, 9, 11, 14, 35, 39, 51}, {0, 1, 9, 20, 23, 41, 51, 53}, {0, 1, 13, 15, 21, 24, 31, 53}.
...
For n = 7..11, that is m = 8, 9, 11, 13, 16, see the W. Lang link.
------------------------------------------------------------------
n = 1, m = 1, v = 3, difference set of type (3, 2, 1): There is only one representative set Sr(2) ={{0, 1}}, and the translates are {1, 2} and {2, 0}, reordered as {0, 2}, giving one class of three difference sets S(3) = {{0, 1}, {0, 2}, {1, 2}} (ordered lexicographically). This describes a triangle, not considered as a projective plane of order m = 1. {0, 1} is a simple difference set because 0 - 1 = -1 == 2 (mod 3), 1 - 0 = 1, and each nonzero element of RS(3) appeared exactly once.
PROG
(PARI) \\ See second Ralf Goertz link
\\ The function a333852_row(m, all=0) computes the complete row corresponding
\\ to a given m of the table if "all" is 1. If "all" is set to 0 a random
\\ choice of one of the normalized difference sets of order m is returned.
CROSSREFS
KEYWORD
nonn,tabf,look
AUTHOR
Wolfdieter Lang, Jul 26 2020
STATUS
approved