Paley's theorem

The Paley theorem , named after the English mathematician Raymond Paley , is a mathematical theorem about the construction of Hadamard block plans using the methods of group theory . As such, it lies in the transition field between combinatorics , geometry and algebra .

Block plans, which can be constructed according to Paley's theorem, are sometimes also referred to as Paley block plans (English Paley designs ) or Paley-Hadamard 2 block plans (English Paley-Hadamard 2 designs ).

Formulation of the sentence

For a prime power of the shape to a natural number, the following always applies: ${\displaystyle q}$ ${\displaystyle q=4n-1}$ ${\displaystyle n\geq 2}$

(I) There is a - block diagram , that is, a symmetric block diagram with the parameters , , , . ${\displaystyle 2{\text{-}}(4n-1,2n-1,n-1)}$ ${\displaystyle t=2}$ ${\displaystyle v=b=q}$ ${\displaystyle k=2n-1={\tfrac {q-1}{2}}}$ ${\displaystyle \lambda =n-1={\tfrac {q-3}{4}}}$

(II) The associated incidence structure can be constructed in the following way: ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$

1. The Galois field to which it belongs is chosen as the point set of ; that is, one chooses the body elements as the points of the incidence structure. ${\displaystyle q}$ ${\displaystyle K=\operatorname {GF} (q)}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathfrak {p}}=K}$
2. For the construction of the block system one starts from the multiplicative group of the Galois body and considers here the subgroup of squares , that is . Then you bet . ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle K^{\times }}$ ${\displaystyle U\leq K^{\times }}$ ${\displaystyle \neq 0}$ ${\displaystyle U=\{u\in K^{\times }\mid \exists x\in K^{\times }:x^{2}=u\}}$ ${\displaystyle {\mathfrak {B}}=\{U+a\mid a\in K\}}$
3. The incidence relation is the element relation , so . ${\displaystyle I}$ ${\displaystyle I=\in }$

Examples of Paley block plans

The two smallest examples of Paley block diagrams are those for the two prime numbers and . ${\displaystyle q=7}$ ${\displaystyle q=11}$

It follows for on the -Blockplan whose geometric structure of the Fano plane corresponds. The subgroup of squares of is described above . ${\displaystyle q=7}$ ${\displaystyle K=\operatorname {GF} (7)}$ ${\displaystyle 2{\text{-}}(7,3,1)}$ ${\displaystyle \operatorname {GF} (7)}$ ${\displaystyle U=\{1,2,4\}}$

For results on the block plan. The subset of the squares of is here . ${\displaystyle q=11}$ ${\displaystyle K=\operatorname {GF} (11)}$ ${\displaystyle 2{\text{-}}(11,5,2)}$ ${\displaystyle \operatorname {GF} (11)}$ ${\displaystyle U=\{1,3,4,5,9\}}$

Further examples result from other articles in the category: Block plan :

→ Main article : (7,3,1) block plan

→ Main article : (11,5,2) block plan

→ Main article : (19,9,4) block plan

→ Main article : (23,11,5) block plan

→ Main article : (31,15,7) block plan

→ Main article : (43,21,10) block plan

→ Main article : (47,23,11) block plan

→ Main article : (59,29,14) block plan

→ Main article : (67,33,16) block plan

Notes on the proof of the theorem

The proof of Paley's theorem can be carried out with the help of Fisher's inequality and the fact that a special permutation group exists which operates twice homogeneously on . ${\displaystyle \Gamma \leq S_{K}}$ ${\displaystyle K}$

As it turns out, the block system can also be described in another way, namely as a set of - images of everything , i.e. in form . ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle \gamma }$ ${\displaystyle U}$ ${\displaystyle \gamma \in \Gamma }$ ${\displaystyle {\mathfrak {B}}=\{\gamma (U)\mid \gamma \in \Gamma \}}$

The permutation group is obtained from the above subgroup by considering those permutations which have the form where and are fixed elements. All these permutations, provided with the usual concatenation , then form . ${\displaystyle \Gamma }$ ${\displaystyle U\leq K^{\times }}$ ${\displaystyle \gamma \colon K\to K}$ ${\displaystyle x\mapsto \gamma (x)=ux+a}$ ${\displaystyle u\in U}$ ${\displaystyle a\in K}$ ${\displaystyle \Gamma }$

It can now be shown that the subgroup has the order , while the order results for the permutation group . So it has odd order and, according to Lagrange's theorem, does not contain an element of order 2 . Hence is , from which then the 2-fold homogeneity of follows. ${\displaystyle U}$ ${\displaystyle k}$ ${\displaystyle \Gamma }$ ${\displaystyle kq={\tfrac {q(q-1)}{2}}}$ ${\displaystyle \Gamma }$ ${\displaystyle -1\notin U}$ ${\displaystyle \Gamma }$

Related result

Another result about Hadamard block plans goes back to Raymond Paley:

For each prime power of the figure a Hadamard block plan exists with the parameters , , , , so a symmetrical -Blockplan. ${\displaystyle q}$ ${\displaystyle q=4n+1}$   ${\displaystyle (n\in \mathbb {N} )}$ ${\displaystyle t=2}$ ${\displaystyle v=b=8n+3}$ ${\displaystyle k=q}$ ${\displaystyle \lambda =2n}$ ${\displaystyle 2{\text{-}}(8n+3,4n+1,2n)}$

This result shows, for example, the existence of the following Hadamard block plans:

→ Main article : (35,17,8) block plan

→ Main article : (51,25,12) block plan

literature

• Thomas Beth , Dieter Jungnickel , Hanfried Lenz : Design Theory . Bibliographical Institute, Mannheim / Vienna / Zurich 1985, ISBN 3-411-01675-2 .
• Albrecht Beutelspacher : Introduction to finite geometry I. Block plans . Bibliographical Institute, Mannheim / Vienna / Zurich 1982, ISBN 3-411-01632-9 . MR0670590
• Peter Dembowski : Finite Geometries (=  results of mathematics and their border areas . Volume 44 ). Springer Verlag, Berlin / Heidelberg / New York 1968.
• Daniel R. Hughes, Fred C. Piper: Design Theory . Cambridge University Press, Cambridge u. a. 1985, ISBN 0-521-25754-9 .
• Konrad Jacobs , Dieter Jungnickel: Introduction to combinatorics (=  de Gruyter textbook ). 2nd, completely revised and expanded edition. de Gruyter, Berlin a. a. 2004, ISBN 3-11-016727-1 .
• Heinz Lüneburg : combinatorics (=  elements of mathematics from a higher point of view . Volume 6 ). Birkhäuser Verlag, Basel / Stuttgart 1971, ISBN 3-7643-0548-7 . MR0335267
• REAC Paley : On orthogonal matrices . In: J. Math. Phys. Mass. Inst. Tech. tape 12 , 1933, pp. 311-320 .

References and comments

1. ↑ A. Beutelspacher: Introduction to finite geometry . 1982, p. 104-108 .
2. ^ H. Lüneburg: combinatorics . 1971, p. 75 ff .
3. ↑ T. Beth, D. Jungnickel, H. Lenz: Design Theory . 1985, p. 70 ff., 262, 264 .
4. ^ DR Hughes, FC Piper: Design Theory . 1985, p. 107 ff .
5. ↑ K. Jacobs, D. Jungnickel: Introduction to combinatorics . 2004, p. 251 ff .
6. ^ P. Dembowski: Finite Geometries . 1968, p. 97 .
7. ^ DR Hughes, FC Piper: Design Theory . 1985, p. 107, 180 .
8. ↑ So . ${\displaystyle q\equiv 3{\pmod {4}}}$
9. ↑ T. Beth, D. Jungnickel, H. Lenz: Design Theory . 1985, p. 262, 264 .
10. ↑ Because of the differences in the presentation in the associated main article, note the reference to the Singer cycle .
11. ↑ All prime powers of gestalt with a base prime also always provide Paley block plans . For example, for the prime powers, one sees  that there is a block plan, a block plan and also a block plan. See also ${\displaystyle q=p^{2j+1}}$   ${\displaystyle (j=0,1,2,3,\dots ),q\geq 7}$ ${\displaystyle p\equiv 3{\pmod {4}}}$ ${\displaystyle p=3}$ ${\displaystyle q=27,243,2187,\dots }$ ${\displaystyle 2{\text{-}}(27,13,6)}$ ${\displaystyle 2{\text{-}}(243,121,60)}$ ${\displaystyle 2{\text{-}}(2187,1093,546)}$
    → Main article : (27,13,6) block plan
12. ↑ The essential step in the proof is to show that the identical mapping of any two-element subset can be fixed, that is, for and the equation always results; s. A. Beutelspacher: Introduction to finite geometry . 1982, p. ${\displaystyle K}$ ${\displaystyle \gamma \in \Gamma }$ ${\displaystyle \{x,y\}\subset K}$   ${\displaystyle (x\neq y)}$ ${\displaystyle \gamma (\{x,y\})=\{x,y\}}$ ${\displaystyle \gamma ={id}_{K}}$ 106 . And also H. Lüneburg: combinatorics . 1971, p. 79 .
13. ↑ K. Jacobs, D. Jungnickel: Introduction to combinatorics . 2004, p. 252 .
14. ↑ T. Beth, D. Jungnickel, H. Lenz: Design Theory . 1985, p. 70-72 .