Counting squares in finite fields (Paley Design)

Question

Consider the following construction due to Paley: Let $q$ be a prime power congruent to 3 modulo 4, and let $Q \subset \mathbb{F}_q$ be the set of nonzero squares (note that $-1 \notin Q$). Call $X = \mathbb{F}_q$ the set of points, and call $\mathfrak{B} = \{ x+Q : x \in \mathbb{F}_q \}$ the set of blocks. I want to show that any pair of two distinct points lie in exactly $(q-3)/4$ blocks. For those interested in design theory: this means that $(X,\mathfrak{B})$ is a combinatorial 2-design with parameters $(q,(q-1)/2,(q-3)/4)$.

It seems that in literature (I saw some google books snippets), this is usually shown by constructing a Hadamard-Matrix first. I was trying to translate such a proof to a direct argument, but apparently I miss something obvious.

---

Here is what I have done so far: Let $\chi \colon \mathbb{F}_q \to \mathbb{Z}$ be the quadratic character, i.e., $\chi(x) = \begin{cases} 0 & x=0\\1 & x \in Q\\ -1 & \text{else} \end{cases}$.

Using that terminology, we have to show that for any distinct pair of points $a,b \in X$ the equation $\chi(a-x) = \chi(b-x) = 1$ holds for exactly $(q-3)/4$ elements $x \in \mathbb{F}_q$.

By the standard properties of $\chi$, one easily calculates $\sum_{x \in \mathbb{F}_q}\chi(a-x)\chi(b-x) = -1$. Since exactly two summands are zero, and all others are $\pm 1$, we see that the summand $-1$ occurs once more than the summand $1$. Consequently, $\chi(a-x) = \chi(b-x)$ holds for exactly $(q-3)/2$ elements $x \in \mathbb{F}_q$. It remains to show that $\chi(a-x) = \chi(b-x) = 1$ happens equally often as $\chi(a-x) = \chi(b-x) = -1$. Note that we have not used $q \equiv 3 \mod 4$ (or equivalently $\chi(-1) = -1$) so far.

I see obvious ways to continue from here, but they seem to lead nowhere. What am I missing?

Answer 1

One way I spotted is to use the fact that $$ (\chi(a-x)+1)(\chi(b-x)+1)=\begin{cases}4,&\ \text{if both $a-x$ and $b-x$ are in $Q$,}\\ 1+\chi(b-a),&\ \text{if $x=a$},\\ 1+\chi(a-b),&\ \text{if $x=b$},\\ 0,&\ \text{otherwise.} \end{cases} $$ As $\chi(-1)=-1$, we have $\chi(b-a)=-\chi(a-b)$. So, if $N$ is the number of elements $x\in\Bbb{F}_q$ such that $a-x,b-x\in Q$, the above observation implies that $$ \begin{aligned} 4N+2&=\sum_{x\in\Bbb{F}_q}(\chi(a-x)+1)(\chi(b-x)+1)\\ &=\sum_{x\in\Bbb{F}_q}(\chi(a-x)\chi(b-x)+\chi(a-x)+\chi(b-x)+1)\\ &=\sum_{x\in\Bbb{F}_q}\chi(a-x)\chi(b-x)\\ &+\sum_{x\in\Bbb{F}_q}\chi(a-x)\\ &+\sum_{x\in\Bbb{F}_q}\chi(b-x)\\ &+\sum_{x\in\Bbb{F}_q}1. \end{aligned} $$ I am fairly sure that you can calculate all the four sums in the last form.

Answer 2

There is a very elegant proof in [Hughes, Piper - Design Theory] which avoids lengthy counting arguments and also provides more insights:

For any odd prime power $q$, we can define an incidence structure $(V,B,\sim)$ in the following way: We set $V = B = \mathbb{F}_q$, and for each "point" $x \in V$ and each "block" $y \in B$ we define $x \sim y$ (and say $x$ is on $y$, or $y$ contains $x$) iff $x-y \in Q$, where $Q = \{ x^2 : x \in \mathbb{F}_q \setminus \{ 0 \} \}$ is the set of nonzero squares in $\mathbb{F}_q$. This structure has $v = q$ points, and $b = q$ blocks, each containing $k = |Q| = (q-1)/2$ points.

This incidence structure has some obvious symmetries: Let $G$ be the group of all permutations on $\mathbb{F}_q$ of the form $x \mapsto ax+b$ with $a \neq 0$, and let $H \leq G$ be the subgroup (of index two) consisting of those permutations where $a \in Q$ is a square. This subgroup preserves the incidence relation, that is, we have $x \sim y \iff f(x) \sim f(y)$ for all $x \in V$, $y \in B$, and $f \in H$.

It is well known (and easy to see) that $G$ is 2-transitive, and, if $q \equiv 3 \mod 4$, $H$ is 2-homogeneous (i.e. transitive on the 2-subsets of $\mathbb{F}_q$): If $\{ x,y \} \subseteq \mathbb{F}_q$ is any 2-subset, there is some permutation $f \in G$ mapping $x$ to $1$ and $y$ to $0$. If $f$ is not in $H$, we compose it with $g \colon x \mapsto -x+1$ (which interchanges $0$ and $1$). Since $q \equiv 3 \mod 4$, $-1$ is not a square in $\mathbb{F}_q$, so $g \in G \setminus H$, and the composition $g \circ f$ will be an element of $H$. In any case $\{ x,y \}$ can be mapped to $\{1,0\}$ by some element of $H$.

Now for arbitrary 2-subsets $\{ x_1,x_2 \}$, $\{ y_1,y_2 \} \subseteq V$, there is some $f \in H$ mapping $\{ x_1,x_2 \}$ to $\{ y_1,y_2 \}$. Since $f$ is an automorphism of the incidence structure, it leads to a bijection between the set of all blocks containing $x_1$ and $x_2$ and the set of all blocks containing $y_1$ and $y_2$. This argument shows that any two points are on a constant number of blocks - say $\lambda$. By a general result, we have $b k (k-1) = \lambda v (v-1)$, and hence $\lambda = (q-3)/4$.

To show that the incidence structure is a 2-$(q,(q-1)/2,(q-3)/4)$-design, it remains to show that it has no repeated blocks (i.e., that each block is uniquely determined by the set of points it contains). This can be done directly without many efforts, but it is much more elegant to cite another general result: All incidence structures with $v$ points, where any two points are on a constant number of blocks, and where at least one block has more than 1 but less than v points have incidence matrices of (full) rank $v$. In particular, there cannot be repeated blocks.

---

This argumentation leads to a general construction of designs from homogeneous permutation groups: If $G$ is any finite permutation group acting $t$-homogeneously on a set $V$, and if $B \subseteq { V \choose k }$ is any set of $k$-subsets of $B$ invariant under $G$ (t < k < |V|) then $(V,B)$ is a $t$-design.

Example: The permutation group $G = \langle (387654), (126)(348) \rangle$ (isomorphic to $\operatorname{PGL}(2,7)$ acting on the projective line) is $3$-transitive on $V = \{1,2,3,4,5,6,7,8\}$ and hence $3$-homogeneous. It has two orbits on the set of $4$-subsets of $V$: one of length $b = 28$, and one of length $b = 42$. By invoking the formula $\lambda = b {k \choose t} / {v \choose t}$, we see that $G$ leads to a $3$-$(8,4,3)$-design, and to a $3$-$(8,4,2)$-design.

The Paley construction is a special case of this construction when $G$ is 2-homogeneous on $V$ but not 2-transitive. Then the stabilizer of $G$ at some point $x \in V$ has exactly two orbits on $V \setminus \{ x \}$, both of the same length $k = (v-1)/2$, where $v = |V|$. Let $B \subseteq {V \choose k}$ be set of all $G$-translates of one of those two orbits. Then, as we have seen before, $(V,B)$ is a $2$-design. Since $G$ is 2-homogeneous, it is also primitive, and hence the stabilizer $G_x$ is a maximal subgroup. Consequently, the block stabililizers are $G$-conjugate to $G_x$, and we have $b = |B| = |G:G_x| = v$. As before, we calculate $\lambda = b {k \choose t} / {v \choose t} = (v-3)/4$. Thus we get a $2$-$(v,(v-1)/2,(v-3)/4)$-design (in particular, $v \equiv 3 \mod 4$).