Exact values and improved bounds on the clique number of cyclotomic graphs

Throughout the paper, we let $p$ be an odd prime, $q$ a power of $p$, $\mathbb{F}_{q}$ the finite field with $q$ elements, and $\mathbb{F}_{q}^{*}=\mathbb{F}_{q}\setminus\{0\}$. We always assume that $d$ is a divisor of $\frac{q-1}{2}$ such that $d>1$.

The goal of this paper is to present new progress toward the estimation of the clique number of cyclotomic graphs, including generalized Paley graphs. We begin by recalling a few basic terminologies. Let $S$ be a subset of $\mathbb{F}_{q}^{*}$ with $S=-S$, the Cayley graph $X=\operatorname{Cay}(\mathbb{F}_{q}^{+};S)$ is the graph with vertex set $\mathbb{F}_{q}$, such that two vertices are adjacent if and only if their difference is in the connection set $S$. We are mostly interested in the case that $X$ is a cyclotomic graph, namely, $S$ is a union of cyclotomic classes, that is, $S$ is a union of cosets of a multiplicative subgroup of $\mathbb{F}_{q}^{*}$. A clique in $X$ is a subset of vertices in $X$ such that every two distinct vertices in the clique are adjacent. The clique number of $X$, denoted by $\omega(X)$, is the size of a maximum clique in $X$. Equivalently, without adopting the graph theory language, the clique number of $X$ is the maximum size of a subset $C$ of $\mathbb{F}_{q}$ such that $C-C\subset S\cup\{0\}$. Thus, estimating the clique number of $X$ is closely related to the additive structure of $S$, and such a problem is central in arithmetic combinatorics especially when $S$ is known to have some multiplicative structure [4].

Cyclotomic graphs are well-studied, especially because they build a bridge among algebraic graph theory, arithmetic combinatorics, number theory, finite geometry, and other subjects (see for example [1, 3, 5, 7, 8, 20]). Among cyclotomic graphs, generalized Paley graphs are of special interest. Let $d>1$ be a positive integer and $q\equiv 1\pmod{2d}$. The $d$-Paley graph on $\mathbb{F}_{q}$, denoted $GP(q,d)$, is the Cayley graph $\operatorname{Cay}(\mathbb{F}_{q}^{+};(\mathbb{F}_{q}^{*})^{d})$, where $(\mathbb{F}_{q}^{*})^{d}=\{x^{d}:x\in\mathbb{F}_{q}^{*}\}$ is the set of $d$-th powers in $\mathbb{F}_{q}^{*}$. It is well-known that $\omega\big{(}GP(q,d)\big{)}\leq\sqrt{q}$; see for example [19, Theorem 1.1]. This square root upper bound on the clique number is often referred to as the trivial upper bound in the literature. In fact, one of the folklore proofs [21, Lemma 1.2] of such a square root upper bound extends to a larger family of Cayley graphs, which we describe below.

This trivial upper bound can be sometimes achieved, for example, if $q$ is a square and $\mathbb{F}_{\sqrt{q}}^{*}\subset S$, then $\mathbb{F}_{\sqrt{q}}$ forms a clique in the corresponding Cayley graph. In particular, if $q$ is a square and $d\geq 2$ is a divisor of $(\sqrt{q}+1)$, then $\omega(GP(q,d))=\sqrt{q}$ [2] (the converse is also true [19]).

Even if $q$ is a non-square, this $\sqrt{q}$ trivial upper bound appears to be the best-known for many families of Cayley graphs. We provide a significant improvement on this bound.

Note that our new upper bound highly depends on the multiplicative structure of the connection set $S$. In the case that $S$ is a union of cyclotomic classes, it is easy to compute the size of the ratio set $S/S$. In particular, Theorem 1.2 implies the following important corollary on the clique number of cyclotomic graphs. While a cyclotomic graph is simply the edge-disjoint union of copies of a given generalized Paley graph, in general it is more complicated to estimate its clique number.

Theorem 1.2 is inspired by the recent breakthrough of Hanson and Petridis [8] on the clique number of generalized Paley graphs. They used Stepanov’s method [15] to show that $\omega\big{(}GP(p,d)\big{)}\leq\sqrt{p/d}+1$ when $q=p$ is a prime. Their method has been extended by Yip to an arbitrary prime power [21, 18] in the following result:

When $q=p$ is a prime, it is easy to verify that the binomial coefficient condition is automatically satisfied. In general, Theorem 1.4 provides an algorithm to give an upper bound on $\omega(GP(q,d))$ by analyzing the base-$p$ representation of $\frac{q-1}{d}$. When $d=2$, which corresponds to Paley graphs, Yip [21] used this idea to proved that $\omega\big{(}GP(q,2)\big{)}\leq\sqrt{q/2}+O(\sqrt{q/p})$ when $q$ is an odd power of a prime $p$. More generally, when $d\mid(p-1)$ and $d\geq 3$, Yip [18, Section 5.2] proved that $\omega\big{(}GP(q,d)\big{)}\leq(1+o(1))\sqrt{q/d}$. However, as remarked in [18, Section 5.2], in general, the analysis is fairly complicated and it is not clear if this approach would always achieve a nontrivial upper bound on the clique number. There are other non-trivial upper bounds on $\omega(GP(q,d))$ in [18], but they are all of the shape $(1-o(1))\sqrt{q}$. To conclude, in general, the best-known upper bound on $\omega(GP(q,d))$ is $(1-o(1))\sqrt{q}$.

Our new results improve the Hanson-Pertidis method and its generalization in the following aspects. Firstly, our results show that the barrier created by the binomial coefficients in Theorem 1.4 can be essentially removed and thus we extend the Hanson-Pertidis bound to all finite fields with non-square order. Note that even if $q$ is assumed to be a non-square, the non-vanishing condition on binomial coefficients cannot be completely removed; a family of counterexamples can be found in Theorem 1.5. More importantly, it seems the Hanson-Pertidis method and its generalization apply only to generalized Paley graphs, while our approach produces a similar upper bound on the clique number of cyclotomic graphs or general Cayley graphs. Interestingly, our proof is based on a “toy version” of Stepanov’s method; see Remark 2.2.

Observe that when $q=p^{3}$ and $d\geq 2$ is a divisor of $p^{2}+p+1$, the subfield $\mathbb{F}_{p}$ forms a clique in $GP(q,d)$ and thus $\omega(GP(q,d))\geq p$; this was first observed by Broere, Döman, and Ridley [2]. It was recently proved that $\mathbb{F}_{p}$ forms a maximal clique in $GP(q,d)$ [22], and it is tempting to conjecture that $\omega(GP(q,d))=p$ since $\mathbb{F}_{p}$ is the only “obvious” large clique. Indeed, when $p=o(d)$, Corollary 1.3 implies that $\omega(GP(q,d))=(1+o(1))p$, as $p,d\to\infty$. This shows that Corollary 1.3 is asymptotically sharp for an infinite family of graphs; this is rather surprising since the Hanson-Petridis bound, despite being the best-known and a highly nontrivial upper bound for $\omega(GP(p,d))$, is far from the conjectural bound $p^{o(1)}$ predicted from the Paley graph conjecture (see for example [19, Section 2.2]). Inspired by this observation, we further discover that the clique number in this setting is in fact exactly $p$.

We remark that Theorem 1.5 is the first nontrivial instance for which the clique number of an infinite family of generalized Paley graphs can be determined, and it refines several results in [2, 20, 22]. More generally, if $GP(q,d)$ admits a clique which is a subfield of $\mathbb{F}_{q}$ and $K$ is the largest such subfield, Yip [22] used character sum estimates to show $K$ is a maximal clique. It is also tempting to conjecture that $\omega(GP(q,d))=|K|$, and we confirm that under some extra assumptions as well as construct several interesting infinite families of such graphs in Section 4.

Theorem 1.2 is a consequence of Theorem 1.7, concerning a new lower bound on the number of directions determined by a Cartesian product. Before stating the new bound, we recall a few basic definitions. Let $AG(2,q)$ denote the affine Galois plane over the finite field $\mathbb{F}_{q}$. Let $U$ be a subset of points in $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. While the connection between the theory of directions and the clique number of generalized Paley graphs was only discovered in recent papers [8, 18], the proof of Lemma 1.1 already indicates such a connection.

When the point set $U$ is a Cartesian product, Di Benedetto, Solymosi, and White [5] proved the following upper bound on the size of $\mathcal{D}_{U}$, improving a result of Rédei [11] and Szőnyi [17] .

They observed that Theorem 1.6 can be used to recover the Hanson-Petridis bound. We refer to [9, 14] for improvements on Theorem 1.6 for the Cartesian product $\{1,2,\ldots,n\}^{2}$ as well as their applications to problems concerning Diophantine equations. Unfortunately, Theorem 1.6 fails to extend to general finite fields due to the subfield obstruction. Yip [18, Theorem 1.6] extended Theorem 1.6 to general finite fields under extra assumptions. However, such extensions are not strong enough for the applications. Overcoming the subfield obstruction, we establish the following lower bound with a “corrected error term” when the point set is a large Cartesian product.

Theorem 1.7 is a generalization of Theorem 1.6. Indeed, when $q=p$ is a prime, we have $s_{1}=s_{2}=0$, and thus Theorem 1.7 recovers Theorem 1.6. Our proof is different from the approach by Di Benedetto, Solymosi, and White [5]; see Remark 2.2. When $q$ is a square, and $A=B=\mathbb{F}_{\sqrt{q}}$ is given by the subfield with size $\sqrt{q}$, the direction set determined by $A\times B$ is $\mathbb{F}_{\sqrt{q}}\cup\{\infty\}$, and our bound gives $q-\sqrt{q}(\sqrt{q}-1)+1=\sqrt{q}+1$, which is sharp. More generally, if $B$ is a subfield of $\mathbb{F}_{q}$ and $A$ is a subspace over $B$ with $|A||B|=q$, our bound is also sharp.

When $|U|\leq q$, the best-known lower bound on $|\mathcal{D}_{U}|$ is roughly of the form $|U|/\sqrt{q}$, due to Dona [6]. While the lower bound given by Theorem 1.7 could be trivial when $A\times B$ is small, we remark that Theorem 1.7 does improve Dona’s bound significantly when $U$ is a large Cartesian product. For example, if $q$ is a non-square, and $\sqrt{q/p}=o(\min\{|A|,|B|\})$, then Theorem 1.7 implies that $A\times B$ determines $(1-o(1))|A||B|$ directions. In particular, we have the following corollary.

Results similar to Corollary 1.8 have played an important role in recent breakthroughs on sum-product type estimates over $\mathbb{F}_{p}$ (see for example [10, 13]). It would be interesting to see if Corollary 1.8 would imply new sum-product type estimates over $\mathbb{F}_{q}$.

Notations. We follow standard notations for arithmetic operations among sets. Given two sets $A$ and $B$, we write $A-B=\{a-b:a\in A,b\in B\}$ and $A/B=\{a/b:a\in A,b\in B\}$.

Structure of the paper. In Section 2, we prove Theorem 1.7. In Section 3, we use Theorem 1.7 to deduce Theorem 1.2. In Section 4, we construct nontrivial families of generalized Paley graphs for which their clique number can be explicitly determined, and deduce Theorem 1.5 as a special case.

Instead of introducing hyper-derivatives and binomial coefficients as in [18, 21], to prove Theorem 1.7, we consider the following lemma, which characterizes polynomials with derivative identically zero. The lemma is well-known, and we include a simple proof.

Next, we present the proof of Theorem 1.7 using Rédei polynomial with Szőnyi’s extension, together with a toy version of Stepanov’s method (see Remark 2.2).

In this section, we use Theorem 1.7 to deduce Theorem 1.2 on the clique number of Cayley graphs.

The next proposition allows us to determine the clique number of families of generalized Paley graphs with exceptionally large cliques. While it is not hard to deduce it from Theorem 1.4, it is rather surprising that Theorem 1.4 could be used to determine the clique number, even for special generalized Paley graphs.

Theorem 1.5 is a special case of Proposition 4.1.

In the next examples, we construct several infinite families of generalized Paley graphs for which Proposition 4.1 is applicable to determine their clique number.

Next, we discuss the necessity of the two assumptions in the statement of Proposition 4.1.

The author thanks Greg Martin and József Solymosi for helpful discussions.