Van Lint–MacWilliams’ conjecture and maximum cliques in Cayley graphs over finite fields

In other words, $P_{q}$ is the graph whose vertices are the elements of $\mathbb{F}_{q}$, such that two vertices are adjacent if and only if the difference between two vertices is a square in $\mathbb{F}_{q}^{\ast}$.

Van Lint–MacWilliams’ conjecture is often phrased as follows: in the Paley graph with order $q^{2}$, the only maximum clique containing $0,1$ is the subfield $\mathbb{F}_{q}$. Van Lint and MacWilliams [vLM78] proved their conjecture in the special case $q=p$. A shorter proof for the case $q=p$ was obtained by Lovász and Schrijver [LS83] using Rédei’s result on the number of directions; see Theorem 3.2 for a related discussion. The conjecture was first proved completely by Blokhuis [Blo84].

Later, Bruen and Fisher [BF91] gave a different proof using the so-called “Jamison method”. Sziklai [Szi99] generalized Blokhuis’s proof and extended the conjecture to certain generalized Paley graphs; see Theorem 2.4. See Remark 2.19 for discussion on the proofs given by Blokhuis and Sziklai, and how they differ from the proof in the present paper.

One can define generalized Paley graphs in an analogous way. They were first introduced by Cohen [SC] in 1988, and reintroduced by Lim and Praeger [LP] in 2009.

In the literature, $3$-Paley graphs and $4$-Paley graphs are also known as cubic Paley graphs and quadruple Paley graphs, respectively.

If $d\mid(q+1)$, the following theorem of Sziklai characterizes all maximum cliques in $GP(q^{2},d)$.

Sziklai [Szi99] also proved the following embeddability result on maximum cliques.

Many authors have attempted to give a new proof of van Lint–MacWilliams’ conjecture. Godsil and Meagher [GM] suggested an approach using algebraic graph theory, in particular the module method, to prove Theorem 2.2. The module method is a powerful tool to prove Erdős-Ko-Rado type theorems; for more details, see the discussion in [GM]*Section 5.9. Recently, Goryainov, Lin, and the authors [AGLY22] have proved that all Peisert-type graphs satisfy the EKR-module property, which is the first step in applying the module method. In addition, the second author [Yip4] gave a Fourier analytic characterization of maximum cliques, which suggests an alternative approach to prove Theorem 2.2.

It is well-known that Paley graphs are self-complementary and symmetric. In [WP2], Peisert discovered a new infinite family of self-complementary symmetric graphs, which he called $P^{*}$-graphs. This new family of graphs also goes under the name of Peisert graphs in the literature.

While the construction of $P^{*}_{q}$ depends on the primitive root $g$, the isomorphism type of $P^{*}_{q}$ is independent of the choice of $g$ [WP2]. Note that $M_{q}$ is not closed under multiplication since $g\cdot g=g^{2}\notin M_{q}$. The condition $p\equiv 3\pmod{4}$ is needed to ensure that $P_{q}^{*}$ is symmetric.

Kisielewicz and Peisert [KP] showed that Paley graphs and Peisert graphs are similar in many aspects. However, we know very little about the structure of cliques of Peisert graphs other than Theorem 2.8.

Motivated by Theorem 2.2 and some numerical evidence, Mullin proposed the following conjecture [NM]*Chapter 8. Note that it is an analog of Theorem 2.2 on the characterization of maximum cliques in a Paley graph with square order.

She remarked that if $q$ is a prime, then Conjecture 2.9 can be proved using a similar technique as Theorem 2.4; see [NM]*Corollary 3.4. She also remarked that the proof of Theorem 2.4 fails to extend to Peisert graphs straightforwardly, since the connection set of a Peisert graph is not closed under multiplication, while for Paley graphs and generalized Paley graphs it is closed; see also Remark 2.19. We show that Conjecture 2.9 holds for sufficiently large $q$; this is Theorem 1.4 and its proof is given in Section 4.

In [Yip4], the second author studied the connection between maximal cliques and maximum cliques in Peisert graphs of order $q^{4}$, and conjectured the following based on numerical evidence.

Note that the Peisert graph of order $q^{4}$ is the edge-disjoint union of two copies of the quadruple Paley graph $GP(q^{4},4)$. Therefore, Conjecture 2.10 strengthens [Yip3]*Theorem 1.6, which states that $\mathbb{F}_{q}$ is a maximal clique in $GP(q^{4},4)$. We show that the conjecture above holds; see Theorem 1.5.

Motivated by the similarity shared among Paley graphs, generalized Paley graphs, and Peisert graphs, Mullin introduced generalized Peisert graphs; see [NM]*Section 5.3. In order to ensure that $GP^{*}(q,d)$ is an undirected graph, we also need a further hypothesis $q\equiv 1\pmod{2d}$; in Mullin’s thesis, this last congruence condition is $q\equiv 1\pmod{d}$, which appears to be a typo.

One motivation of this paper is to provide a new and short proof for Theorem 2.4, and explore the structure of maximum cliques of those Cayley graphs which are similar to Paley graphs and generalized Paley graphs. In particular, we consider Cayley graphs defined on $\mathbb{F}_{q^{2}}^{+}$ with connection set being a union of cosets of $\mathbb{F}_{q}^{*}$ in $\mathbb{F}_{q^{2}}^{*}$ as in equation (1).

In our Definition 1.1 of a Peisert-type graph $X=\operatorname{Cay}(\mathbb{F}_{q^{2}}^{+},S)$ we assume that $\mathbb{F}_{q}\subset S$; in particular, these graphs enjoy the property that $\omega(X)\geq q$. As we will see in the proof of Theorem 1.2, the condition on the number of cosets $m\leq\frac{q+1}{2}$ is needed. Another reason for assuming $m\leq\frac{q+1}{2}$ is that we want $|S|\leq\frac{q^{2}-1}{2}$; see Example 2.18.

We remark that our definition of Peisert-type graphs shares some similarities with the definition of Peisert graphs. Recall that a Peisert graph is simply an edge-disjoint union of two copies of the quadruple Paley graph with the same order. Note that $\operatorname{Cay}(\mathbb{F}_{q^{2}}^{+},\mathbb{F}_{q}^{*})=GP(q^{2},q+1)$ is a $(q+1)$-Paley graph. Therefore, a Peisert-type graph is simply an edge-disjoint union of copies of $(q+1)$-Paley graph. Notice also that we do not require the connection set $S$ to be closed under multiplication in Definition 1.1.

The following lemma allows us to unify the notions of generalized Paley graphs $GP(q^{2},d)$ and generalized Peisert graphs $GP^{*}(q^{2},d)$ under the assumption that $d\mid(q+1)$. Note that when $d$ is even, $GP(q,d)$ already embeds inside $GP^{\ast}(q,d)$; however, for odd $d$, there is no such obvious embedding as $GP^{\ast}(q,d)$ is defined only for even values of $d$. The lemma shows that the Peisert-type graph is general enough to encompass both cases.

The proof of the preceding lemma will be presented in Section 4. Both (generalized) Paley graphs and (generalized) Peisert graphs have many nice properties, and they have many applications in coding theory and design theory; see for example [JAlex15, JL, KR, WQWX]. We also expect that Peisert-type graphs will have a new set of applications.

Our goal is to characterize maximum cliques in a Peisert-type graph $X=\operatorname{Cay}(\mathbb{F}_{q^{2}}^{+},S)$. Our first main result, Theorem 1.2, asserts that the clique number of $X$ is $q$, and every maximum clique in $X$ has vector space structure; see [Yip3] for a related discussion on the vector space structure of maximal cliques in Cayley graphs. Later, we will show that such subspace must be in fact the subfield $\mathbb{F}_{q}$ under additional assumptions.

When the order of the graph is $p^{2}$, Theorem 1.2 immediately implies the following corollary.

It is natural to ask whether the conclusion in Theorem 1.2 can be strengthened to the assertion that any maximum clique is an $\mathbb{F}_{q}$-affine space. In Example 2.21 below, we will see a counterexample for this stronger conclusion.

In the same spirit as Theorem 2.6, we prove an embeddability result for cliques in Peisert-type graphs.

We want to find minimal assumptions on Peisert-type graphs $X=\operatorname{Cay}(\mathbb{F}_{q^{2}}^{+},S)$ for which the only maximum clique containing $0,1$ is the subfield $\mathbb{F}_{q}$. Such a clique is already an $\mathbb{F}_{p}$-subspace by Theorem 1.2, and to show that it is exactly the subfield $\mathbb{F}_{q}$, we will use character sum estimates in Section 3.2. The following definition is helpful for our discussion.

Our Theorem 1.3 has the hypothesis that $\{\chi(x):x\in S\}$ is $\varepsilon$-lower bounded for some $\varepsilon>0$. The following example explains the necessity of the condition $m\leq(q+1)/2$, or equivalently, $|S|\leq(q^{2}-1)/2$ in Definition 1.1.

In Lemma 2.13, we saw that certain generalized Paley graphs and Peisert graphs are Peisert-type graphs. Next we present two quick applications of Theorem 1.3.

It is straightforward to apply Theorem 1.3 to generalized Paley graph $GP(q^{2},d)$, where $d\mid(q+1)$. Let $\chi$ to be a multiplicative character with order $d$; then the set $\{\chi(x^{d}):x\in\mathbb{F}_{q^{2}}^{*}\}=\{1\}$ is trivially $1$-lower bounded. This immediately implies a slightly weaker version of Theorem 2.4, that is, we obtain a simple proof that Theorem 2.4 holds if $p$ is sufficiently large.

Similarly, we can apply Theorem 1.3 to Peisert graph with order $q^{2}$, where $q\equiv 3\pmod{4}$, and deduce that Conjecture 2.9 holds as long as $p$ is sufficiently large.

In Section 4.3, we will apply Theorem 1.3 to study maximum cliques in a generalized Peisert graph $GP^{*}(q^{2},d)$, where $d\mid(q+1)$. Note that Theorem 2.20 is a generalization of Theorem 1.4. It also strengthens Sziklai’s result (Theorem 2.4), because $GP(q^{2},d)$ is a subgraph of $GP^{*}(q^{2},d)$; see Remark 2.12 for more details.

The following example illustrates the necessity of the assumption that $p$ is sufficiently large stated in Theorem 1.3.

Let $AG(2,q)$ denote the affine Galois plane over the finite field $\mathbb{F}_{q}$. Let $U\subset AG(2,q)$. We use Cartesian coordinates in $AG(2,q)$ so that $U=\{(x_{i},y_{i}):1\leq i\leq|U|\}$. The set of directions determined by $U\subset AG(2,q)$ is

where $\infty$ is the vertical direction. The theory of directions has been developed by Rédei [LR73], Szőnyi [Sz], and many other authors. The main methods in the theory revolve around studying certain lacunary polynomials and symmetric polynomials. In modern language, the theory was built via the application of the polynomial method over finite fields. We remark that it has been used several times to study cliques of Paley graphs and generalized Paley graphs. One highlight is that it can be used to deduce the best-known upper bounds on the clique number of Paley graphs and generalized Paley graphs; see recent papers [DSW, Yip2].

The standard way to identify $\mathbb{F}_{q^{2}}$ and $AG(2,q)$ is via an embedding with respect to a basis of $\mathbb{F}_{q^{2}}$ over $\mathbb{F}_{q}$ seen as a $2$-dimensional vector space over $\mathbb{F}_{q}$. We say that $\pi:\mathbb{F}_{q^{2}}\to AG(2,q)$ is an embedding if

where $\{u,v\}$ forms a basis of $\mathbb{F}_{q^{2}}$ over $\mathbb{F}_{q}$. In the definition below, the term $F$-subspace means a vector subspace defined over a field $F$.

The following theorem, due to Ball [Ball03], characterizes the number of directions determined by the graph of a function. It was built on previous works [LR73, BBS, BBBSS]. We present below the simplified version of Ball’s original formulation.

If $U\subset AG(2,q)$ and $|U|=q$, we can try to apply Theorem 3.2 to study $\mathcal{D}_{U}$. This is because an affine transformation preserves the number of directions; if $U$ does not determine all the directions, then $U$ is a graph of a function after an affine transformation. The following stability result, due to Szőnyi [Sz1] and Sziklai [Szi99], enables us to extend Theorem 3.2 to any $U\subset AG(2,q)$ with size $q-O(\sqrt{q})$.

Recall that a multiplicative character of $\mathbb{F}_{q}$ is a group homomorphism from $\mathbb{F}_{q}^{*}$ to the multiplicative group of complex numbers with modulus 1. It is customary to define $\chi(0)=0$. We will use $\chi_{0}$ to denote the trivial multiplicative character of $\mathbb{F}_{q}$. For a multiplicative character $\chi$, its order $d$ is the smallest positive integer such that $\chi^{d}=\chi_{0}$.

Many problems in number theory and combinatorics rely on non-trivial character sum estimates over certain subsets of interest. We refer to [Chang] for a nice survey paper by Chang, consisting of known results on character sums over a subset of a given finite field, such as the extension of the classical Pólya-Vinogradov inequalities and Burgess’ bounds to a general finite field. For our purpose, we need nontrivial character sum estimates over a subspace of a finite field.

Weil’s estimate (see [LN]*Theorem 5.41) is a classical tool of bounding complete character sums with a polynomial argument over a finite field. The following theorem, due to Katz [Katz], essentially generalizes Weil’s estimate to character sums over a subspace. Recall an element $\theta\in\mathbb{F}_{q^{n}}$ is said to have degree $k$ over $\mathbb{F}_{q}$ if $\mathbb{F}_{q^{k}}$ is the smallest extension of $\mathbb{F}_{q}$ that contains $\theta$.

Recently, Reis [Reis] used Theorem 3.4 to prove the following character sum estimate over an affine space.

The hypothesis on the existence of a degree $n$ element cannot be completely dropped. For equation (2) to hold, we must have some assumptions on the structure of the affine space $\mathcal{A}$. Typically, we need to assume that $\mathcal{A}$ does not have a special algebraic structure. As a counter-example, let $\mathcal{A}=\mathcal{V}=\mathbb{F}_{q^{t}}$ be a proper subfield. Then we can find a non-trivial multiplicative character $\chi$ on $\mathbb{F}_{q^{n}}$ such that $\chi|_{A}$ is the trivial character; in this case, $\sum_{a\in\mathcal{A}}\chi(a)=q^{t}-1>nq^{t-1/2}$ holds for sufficiently large $q$, violating the conclusion in Theorem 3.5. This construction is an example of the so-called subfield obstruction.

Chang [Chang]*Section 5 also gave a somewhat weaker nontrivial estimate of character sums over subspaces of finite fields. Here we use Theorem 3.5 since it is stronger to some extent, and it does not involve any implicit constants, which can be challenging to determine.

The following corollary gives a non-trivial upper bound on the character sums over a subspace when $\mathcal{A}$ is a subspace but not a subfield. Corollary 3.6 is a consequence of Theorem 3.5 and [Reis]*Proposition 2.2; here we include the proof for the sake of completeness.

Note that if $n$ is an odd prime, then any element in $\mathbb{F}_{q^{n}}\setminus\mathbb{F}_{q}$ has degree $n$. Thus, we obtain the following corollary of Theorem 3.5, which will be used in Section 5.

As a motivation for Definition 1.1, Lemma 2.13 states that (generalized) Paley and Peisert graphs are special instances of Peisert-type graphs.

With the two tools described in the previous section, we are ready to prove Theorem 1.2.

Inspired by the proof of Theorem 1.2, we provide a sufficient condition for a maximum clique in a Peisert-type graph on $\mathbb{F}_{q^{2}}$ to be the subfield $\mathbb{F}_{q}$.