Introduction
The independence number of a graph G G G , denoted by α ( G ) \alpha(G) α ( G ) , is one of the most studied parameters in graph theory. Since it is NP-hard to compute [36 ] and to approximate [55 ] , a lot of effort has been put into finding good bounds on the independence number. The spectral approach has yielded many such bounds. The spectrum Spec ( G ) \operatorname{Spec}(G) Spec ( G ) of a graph G G G is the multiset of the eigenvalues of its adjacency matrix, which can be ordered as
λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n \lambda_1 \ge\lambda_2 \ge\cdots\ge\lambda_n λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n
Two of the most well-known types of spectral bounds are ratio bounds (that use the ratio between the largest and smallest eigenvalues), and inertia bounds (that count the signs of the eigenvalues). While the ratio bounds are relatively well understood [28 , 33 , 54 ] , the inertia bounds are much less well understood.
The first inertia bound was introduced in its unweighted form by Cvetković [23 ] in 1971. This bound was strong enough to give an algebraic proof of the Erdős-Ko-Rado theorem, which can also be obtained using the ratio bound, see e.g. [32 ] . However, the full power of the bound lies in the freedom to choose weights. Calderbank and Frankl [20 ] studied the weighted version of the inertia bound in 1992 in order to derive multiple results in extremal set theory. For a Hermitian matrix M M M , we let n ≥ 0 ( M ) n_{\ge0}(M) n ≥ 0 ( M ) be the number of non-negative eigenvalues of M M M (counted with multiplicity). For a graph G G G a weighted adjacency matrix of G G G is a Hermitian matrix B B B with zero diagonal where B i j = 0 B_{ij}=0 B ij = 0 when there is no edge i ∼ j i\sim j i ∼ j in G G G .
Theorem 1 (Weighted inertia bound, cf. [20 ] ). For a graph G G G and a weighted adjacency matrix B B B ,
α ( G ) ≤ n ≥ 0 ( B ) . \alpha(G) \le n_{\ge0}(B). α ( G ) ≤ n ≥ 0 ( B ) .
We let n ≥ 0 ( G ) n_{\ge0}(G) n ≥ 0 ( G ) denote the optimal bound on α ( G ) \alpha(G) α ( G ) obtained using Theorem 1 . The strength of this bound is such that it is tight for every graph on at most 10 vertices [25 ] . The search space of weights is infinite and there is no practical program known to find optimal weights. There are some heuristics known, such as for Cayley graphs in [46 ] , but no method that guarantees optimality. This also makes it hard to lower bound n ≥ 0 ( G ) n_{\ge0}(G) n ≥ 0 ( G ) by anything larger than α ( G ) \alpha(G) α ( G ) .
In 2018 Sinković published the first example where using real weights cannot give a matrix such that n ≥ 0 ( B ) n_{\ge0}(B) n ≥ 0 ( B ) is equal to the independence number [47 ] . Only in the last two years has the separation between α ( G ) \alpha(G) α ( G ) and n ≥ 0 ( G ) n_{\ge0}(G) n ≥ 0 ( G ) been stretched to arbitrarily large gaps. Kwan and Wigderson used ideas from probability theory to show that C 4 C_4 C 4 -free graphs have a weighted inertia bound that grows linearly in the order n n n [41 ] . Such graphs can have ratio bound and hence independence number bounded by O ( n 3 / 4 ) O(n^{3/4}) O ( n 3/4 ) . Elphick, Tang and Zhang [49 ] showed that there is no way to upper bound n ≥ 0 ( G ) n_{\ge0}(G) n ≥ 0 ( G ) in terms of α ( G ) \alpha(G) α ( G ) by demonstrating a family of graphs with fixed independence number, α ( G ) = 2 \alpha(G)=2 α ( G ) = 2 , where the weighted inertia bound grows at a rate Ω ( n 1 / 9 ) \Omega(n^{1/9}) Ω ( n 1/9 ) . In this paper we continue their line of work and show similar separation results for the more general k k k -independence number of a graph.
The k k k -independence number of a graph G G G , denoted α k ( G ) \alpha_k(G) α k ( G ) , is a natural generalization of the independence number that considers sets where all vertices are at distance greater than k k k from each other. This more general independence parameter is also NP-hard to compute, see [40 ] . Equivalently, it can be defined as the independence number of G k G^k G k , the k k k -th graph power of G G G , the graph on the same vertex set as G G G where two vertices are adjacent if they are at distance at most k k k in G G G .
Graph powers help design efficient algorithms for specific combinatorial optimization problems, see [13 , 17 ] . In distributed computing, the k k k -th power of graph G G G represents the possible flow of information during k k k rounds of communication in a distributed network of processors organized according to a graph G G G , see [44 ] . The investigation of the behavior of the independence number of graph powers is motivated by questions in (quantum) information theory and coding theory. Indeed, α k ( G ) \alpha_k(G) α k ( G ) and hence inertia bounds can be used to estimate the possible size of minimum distance k + 1 k+1 k + 1 codes, see e.g. [5 , 6 ] . The inertia can also be used to upper bound the quantum k k k -independence number [52 ] and the quantum distance-k k k chromatic number [4 , 8 ] , which is particularly helpful because these parameters are not known to be computable.
Good inertia bounds typically require a good choice of weights. For graphs of interest this is much more difficult to find for G k G^k G k , than for G G G , because the graph is denser and thus has more freedom in its choice of weights. This led Abiad, Coutinho and Fiol [2 ] to introduce a more restricted weight optimization version of the inertia bound, which bounds α k ( G ) \alpha_k(G) α k ( G ) directly in terms of the spectrum of G G G . Note that the relation between G G G and G k G^k G k is not particularly algebraic, so their spectra are in general not related, see e.g. [3 , 24 , 53 ] . Therefore bounds on α k \alpha_k α k which use the spectrum of G G G directly (such as the following bound) carry different information than those using the spectrum of G k G^k G k .
Theorem 2 (Inertia-type bound [2 ] ). Let P k \mathcal{P}_k P k denote the vector space of real polynomials in x x x with degree at most k k k . Let p ∈ P k p \in\mathcal{P}_k p ∈ P k and λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n \lambda_1 \ge\lambda_2 \ge\cdots\ge\lambda_n λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n be the eigenvalues of the adjacency matrix A A A of G G G . Let w ( p ) = min i ( p ( A ) ) i i w(p) = \min_i(p(A))_{ii} w ( p ) = min i ( p ( A ) ) ii and W ( p ) = max i ( p ( A ) ) i i W(p) = \max_i(p(A))_{ii} W ( p ) = max i ( p ( A ) ) ii denote the minimum and maximum of the diagonal of p ( A ) p(A) p ( A ) and
In k ( p , G ) : = min { ∣ { i : p ( λ i ) ≥ w ( p ) } ∣ , ∣ { i : p ( λ i ) ≤ W ( p ) } ∣ } . \operatorname{In}_k(p,G) := \min\left\{\left|\{i : p(\lambda_i) \ge w(p)\}\right|,\left|\{i : p(\lambda_i) \le W(p)\}\right|\right\}. In k ( p , G ) := min { ∣ { i : p ( λ i ) ≥ w ( p )} ∣ , ∣ { i : p ( λ i ) ≤ W ( p )} ∣ } . Then α k ( G ) ≤ In k ( p , G ) \alpha_k(G) \le\operatorname{In}_k(p,G) α k ( G ) ≤ In k ( p , G ) .
We write In k ( G ) \operatorname{In}_k(G) In k ( G ) for the optimal inertia-type bound, i.e., using the optimal polynomial. Even less is known about the performance of this inertia-type bound. Finding In k ( G ) \operatorname{In}_k(G) In k ( G ) can be formulated as a mixed-integer linear program [3 ] , which can be solved in polynomial time for fixed k k k [7 ] . Nevertheless, relatively little is known about the graphs for which the optimum equals α k ( G ) \alpha_k(G) α k ( G ) . Indeed, we do not know when the inertia-type bound is tight, except for one class of graphs attaining equality for p = x k p=x^k p = x k [1 ] and for specific Odd graphs [3 ] .
In this paper we show that large separation exists between the k k k -independence number and inertia bounds. We show this for both the weighted inertia bound on G k G^k G k and for the inertia-type bound on G G G . During the preparation of this paper, it was shown that the weighted inertia bound is at least as strong as the inertia-type bound [31 ] . Indeed, the separation we show for the inertia-type bound is larger. In § 2 we use the approach from [49 ] to deduce separation results for the weighted inertia bound. In particular, we prove separation for random graphs (Corollary 5) and show that certain non-explicit Cayley graphs have α k ( G ) = 2 \alpha_k(G)=2 α k ( G ) = 2 , but have n ≥ 0 ( G k ) = Ω ~ ( n 1 / ( 6 k ) ) n_{\ge0}(G^k)=\tilde{\Omega}(n^{1/(6k)}) n ≥ 0 ( G k ) = Ω ~ ( n 1/ ( 6 k ) ) .
Theorem 14. For fixed k ≥ 3 k \ge3 k ≥ 3 there is a sequence of graphs G n G_n G n of order N N N such that α k ( G n ) = 2 \alpha_k(G_n)=2 α k ( G n ) = 2 and n ≥ 0 ( G n k ) ≥ Ω ~ ( N 1 / ( 6 k ) ) n_{\ge0}(G_n^k) \ge\tilde{\Omega}(N^{1/(6k)}) n ≥ 0 ( G n k ) ≥ Ω ~ ( N 1/ ( 6 k ) ) .
Separation also holds for k = 2 k=2 k = 2 , but our proof does not give the same 1 6 k \frac{1}{6k} 6 k 1 exponent. We cannot extend Kwan and Wigderson’s result [41 ] to get a linearly growing weighted inertia bound, because graph powers are not C 4 C_4 C 4 -free and are generally locally dense. Instead, the proof of our separation result relies on the observation that all large enough subsets of certain Abelian groups can be written as a sumset A + A A+A A + A . This follows from an extension of Alon’s result on this topic in [10 ] to symmetric sets and larger sums k A kA k A , see Theorem 6 , which may be a result of independent interest. A month before the appearance of this preprint, Chae and Lee posted an article that also obtained the extension of Alon’s result to larger k k k but without symmetry [21 ] . In § 3 we show that the inertia-type bound can grow linearly with the order while the diameter is at most k k k (implying α k ( G ) = 1 \alpha_k(G)=1 α k ( G ) = 1 ). We show this for random graphs of the right density (Corollary 17) and inspired by the recent construction of pseudorandom graphs by Forey, Fresán, Kowalski and Wigderson in [29 ] we also give explicit vertex-transitive graphs for which this holds.
Theorem 18. Fix an integer k ≥ 5 k \ge5 k ≥ 5 and prime p > k p > k p > k . Define s = ⌊ k 2 ⌋ + 1 s=\left\lfloor\frac{k}{2}\right\rfloor+1 s = ⌊ 2 k ⌋ + 1 . There exists an integer a ≥ 1 a \ge1 a ≥ 1 such that s ∣ p 2 a − 1 s \mid p^{2a}-1 s ∣ p 2 a − 1 . For any large enough prime power q = ( p 2 a ) h q=(p^{2a})^h q = ( p 2 a ) h the graph
G q s : = Cay ( F q s , S s ) , where S s = { ± ( t , t 2 , … , t s ) : t ∈ F q × } G_q^s:=\operatorname{Cay}(\mathbb{F}_q^s,S_s),\qquad\text{where }S_s=\{\pm(t,t^2,\ldots,t^s):t\in\mathbb{F}_q^\times\} G q s := Cay ( F q s , S s ) , where S s = { ± ( t , t 2 , … , t s ) : t ∈ F q × } has
α k ( G q s ) = 1 , and In k ( G q s ) = Ω ( ∣ V ( G q s ) ∣ ) as q → ∞ . \alpha_k(G_q^s)=1,\qquad\text{and}\qquad\operatorname{In}_k(G_q^s)=\Omega(|V(G_q^s)|)\text{ as }q\to\infty. α k ( G q s ) = 1 , and In k ( G q s ) = Ω ( ∣ V ( G q s ) ∣ ) as q → ∞.
The same separation result also holds for 2 ≤ k ≤ 4 2 \le k \le4 2 ≤ k ≤ 4 , but requires different graphs and a different proof, which we only remark upon.
Notation
The following two sections can be read independently. Therefore each of them will contain its own necessary preliminaries. In both sections we prove results for the Erdős-Rényi random graph. We let G ( n , p ) G(n,p) G ( n , p ) denote this random graph on n n n vertices where each edge is included independently with probability p p p . The results we prove will be asymptotic. We use the following notation. For two positive functions f , g : N → R > 0 f,g:\mathbb{N}\to\mathbb{R}_{>0} f , g : N → R > 0 we write f = o ( g ) f=o(g) f = o ( g ) , ω ( g ) \omega(g) ω ( g ) , O ( g ) O(g) O ( g ) or Ω ( g ) \Omega(g) Ω ( g ) if the fraction f ( n ) g ( n ) \frac{f(n)}{g(n)} g ( n ) f ( n ) as n → ∞ n\to\infty n → ∞ goes to zero or infinity, is bounded from above or bounded from below by a constant C > 0 C>0 C > 0 respectively. If f = O ( g ) f=O(g) f = O ( g ) and f = Ω ( g ) f=\Omega(g) f = Ω ( g ) we write f = Θ ( g ) f=\Theta(g) f = Θ ( g ) . We also use f = O ~ ( g ) f=\widetilde{O}(g) f = O ( g ) if f ( n ) = O ( g h ) f(n)=O(gh) f ( n ) = O ( g h ) where h h h is a polylogarithmic function. The notation Ω ~ \widetilde{\Omega} Ω is used analogously. We use log \log log to denote logarithms with base 2 2 2 and ln \ln ln for natural logarithms. Lastly, we say that a sequence of events E n E_n E n occurs with high probability if P ( E n ) = 1 − o ( 1 ) \mathbb{P}(E_n)=1-o(1) P ( E n ) = 1 − o ( 1 ) as n → ∞ n\to\infty n → ∞ .
Separation of the weighted inertia bound
Recall that n ≥ 0 ( G ) n_{\ge0}(G) n ≥ 0 ( G ) denotes the optimal weighted inertia bound for a graph G G G . In [49 ] the authors lower bounded n ≥ 0 ( G ) n_{\ge0}(G) n ≥ 0 ( G ) for complements of pseudorandom graphs. We use this lower bound to find separation results for the weighted inertia bound of random graphs and graph powers. Let λ ( G ) \lambda(G) λ ( G ) denote max { ∣ λ 2 ( G ) ∣ , ∣ λ n ( G ) ∣ } \max\{|\lambda_2(G)|,|\lambda_n(G)|\} max { ∣ λ 2 ( G ) ∣ , ∣ λ n ( G ) ∣ } , the second largest absolute value of an eigenvalue. A graph is an ( n , d , λ ) (n,d,\lambda) ( n , d , λ ) -graph if it has order n n n , is d d d -regular and has λ ( G ) ≤ λ \lambda(G)\le\lambda λ ( G ) ≤ λ .
Theorem 3 ([49 ] ). Suppose G = ( V , E ) G=(V,E) G = ( V , E ) is an n n n -vertex graph, such that its complement contains an ( n , d , λ ) (n,d,\lambda) ( n , d , λ ) -graph Γ \Gamma Γ as a spanning subgraph with d < n 2 − 1 d<\frac{n}{2}-1 d < 2 n − 1 . Then we have
n ≥ 0 ( G ) ≥ ( d + λ 8 λ ) 1 / 3 . n_{\ge0}(G)\ge\left(\frac{d+\lambda}{8\lambda}\right)^{1/3}. n ≥ 0 ( G ) ≥ ( 8 λ d + λ ) 1/3 .
In [41 ] Kwan and Wigderson conjectured that the weighted inertia bound is typically Ω ( n log n ) \Omega\left(\frac{n}{\log n}\right) Ω ( l o g n n ) . As a consequence of Theorem 3 , we show a lower bound of Ω ( ( n / log n ) 1 / 6 ) \Omega\left((n/\log n)^{1/6}\right) Ω ( ( n / log n ) 1/6 ) in § 2.1 , see Corollary 5. We rely on known results that a random graph is a spectral expander and contains many Hamilton cycles.
Theorem 3 was used in [49 ] to show that the complements of Alon’s construction of triangle-free pseudorandom graphs [9 ] are examples of graphs with α ( G ) = 2 \alpha(G)=2 α ( G ) = 2 and n ≥ 0 ( G ) = Ω ( n 1 / 9 ) n_{\geq0}(G)=\Omega(n^{1/9}) n ≥ 0 ( G ) = Ω ( n 1/9 ) . In § 2.3 we show a similar separation result for graph powers.
It can be shown that the graphs arising as the k k k th power of a graph form only a small fraction of all graphs and hence it seems reasonable that the separation should become smaller as k k k increases. We could not prove that the complements of Alon’s triangle-free graphs [9 ] are graph powers for any k ≥ 2 k\geq2 k ≥ 2 and large n n n . Therefore we could not rely on these graphs to give separation results. Instead, we rely on random Cayley graphs to give graphs G k G^k G k with large separation. These graphs still have unbounded weighted inertia bound while α k ( G ) = 2 \alpha_k(G)=2 α k ( G ) = 2 . To show that they arise as graph powers we first need to extend Alon’s result on sumsets, specifically Theorem 2.1 in [10 ] , which we extend in § 2.2 .
The weighted inertia bound is far from tight in random graphs
Lemma 4. If G ∼ G ( n , 1 2 ) G\sim G(n,\frac{1}{2}) G ∼ G ( n , 2 1 ) , then G G G contains a ( n , n 2 − O ( n log n ) , O ( n log n ) ) (n,\frac{n}{2}-O(\sqrt{n\log n}),O(\sqrt{n\log n})) ( n , 2 n − O ( n log n ) , O ( n log n )) -graph with high probability.
Proof. It is known that G ( n , p ) G(n,p) G ( n , p ) contains ⌊ δ ( G ) 2 ⌋ \left\lfloor\frac{\delta(G)}{2}\right\rfloor ⌊ 2 δ ( G ) ⌋ edge-disjoint Hamilton cycles if p p p is far enough from 0 and 1 [39 theorem 2] . In particular, this holds for p = 1 2 p=\frac{1}{2} p = 2 1 . It is well-known that with high probability all degrees of a random G ( n , 1 2 ) G(n,\frac{1}{2}) G ( n , 2 1 ) graph lie within O ( n log n ) O(\sqrt{n\log n}) O ( n log n ) of n 2 \frac{n}{2} 2 n and that the minimum degree δ ( G ) < n 2 \delta(G)<\frac{n}{2} δ ( G ) < 2 n . Therefore the union of the Hamilton cycles forms a 2 ⌊ δ ( G ) 2 ⌋ = n 2 − O ( n log n ) ≤ n 2 − 1 2\left\lfloor\frac{\delta(G)}{2}\right\rfloor=\frac{n}{2}-O(\sqrt{n\log n})\leq\frac{n}{2}-1 2 ⌊ 2 δ ( G ) ⌋ = 2 n − O ( n log n ) ≤ 2 n − 1 regular spanning subgraph Γ \Gamma Γ . Let G ′ G' G ′ be the graph that is G ∖ Γ G\setminus\Gamma G ∖ Γ . Then G ′ G' G ′ is a graph with maximum degree at most Δ ( G ) − δ ( G ) + 1 \Delta(G)-\delta(G)+1 Δ ( G ) − δ ( G ) + 1 . Hence λ 1 ( G ′ ) = O ( n log n ) \lambda_1(G')=O(\sqrt{n\log n}) λ 1 ( G ′ ) = O ( n log n ) . Moreover, from the characterization using Rayleigh quotients it follows that ∣ λ i ( G ) − λ i ( Γ ) ∣ ≤ λ 1 ( G ′ ) \lvert\lambda_i(G)-\lambda_i(\Gamma)\rvert\leq\lambda_1(G') ∣ λ i ( G ) − λ i ( Γ )∣ ≤ λ 1 ( G ′ ) , so G G G and Γ \Gamma Γ have nearly the same spectrum. Using the known result that λ ( G ) = O ( n ) \lambda(G)=O(\sqrt{n}) λ ( G ) = O ( n ) with high probability [30 ] , we find that λ ( Γ ) ≤ O ( n ) + O ( n log n ) = O ( n log n ) \lambda(\Gamma)\leq O(\sqrt{n})+O(\sqrt{n\log n})=O(\sqrt{n\log n}) λ ( Γ ) ≤ O ( n ) + O ( n log n ) = O ( n log n ) .
Corollary 5. If G ∼ G ( n , 1 2 ) G\sim G(n,\frac{1}{2}) G ∼ G ( n , 2 1 ) , then with high probability n ≥ 0 ( G ) = Ω ( ( n log n ) 1 / 6 ) n_{\geq0}(G)=\Omega\left(\left(\frac{n}{\log n}\right)^{1/6}\right) n ≥ 0 ( G ) = Ω ( ( l o g n n ) 1/6 ) .
Proof. Note that the distribution of the complement of G G G is the same as the distribution of G G G , so it follows from Lemma 4 that the complement of G G G contains a ( n , n 2 − O ( n log n ) , O ( n log n ) ) (n,\frac{n}{2}-O(\sqrt{n\log n}),O(\sqrt{n\log n})) ( n , 2 n − O ( n log n ) , O ( n log n )) -subgraph. By Theorem 3 we get
n ≥ 0 ( G ) ≥ ( n 2 − O ( n log n ) + O ( n log n ) O ( n log n ) ) 1 / 3 = Ω ( ( n log n ) 1 / 6 ) . n_{\geq0}(G)\geq\left(\frac{\frac{n}{2}-O(\sqrt{n\log n})+O(\sqrt{n\log n})}{O(\sqrt{n\log n})}\right)^{1/3}=\Omega\left(\left(\frac{n}{\log n}\right)^{1/6}\right). n ≥ 0 ( G ) ≥ ( O ( n log n ) 2 n − O ( n log n ) + O ( n log n ) ) 1/3 = Ω ( ( log n n ) 1/6 ) .
This already shows that the weighted inertia bound is far from tight for most graphs, as α ( G ) = ( 2 + o ( 1 ) ) log n \alpha(G)=(2+o(1))\log n α ( G ) = ( 2 + o ( 1 )) log n for G ∼ G ( n , 1 2 ) G\sim G(n,\frac{1}{2}) G ∼ G ( n , 2 1 ) with high probability [18 Chapter 11] .
Large sets in finite vector spaces are k-sumsets
Define k A kA k A to be the set of sums of exactly k k k elements of A A A , allowing repetitions, i.e. the set { a 1 + ⋯ + a k : a i ∈ A } \{a_1+\cdots+a_k : a_i \in A\} { a 1 + ⋯ + a k : a i ∈ A } . In this section we extend Alon’s sufficient condition for a set to be a sumset [10 ] to k > 2 k>2 k > 2 . In particular, we prove the following:
Theorem 6. Fix an integer k ≥ 2 k \ge2 k ≥ 2 . Let q > k q > k q > k be a prime number, Γ = ( Z / q Z ) n \Gamma= (\mathbb{Z}/q\mathbb{Z})^n Γ = ( Z / q Z ) n , and N : = ∣ Γ ∣ N := |\Gamma| N := ∣Γ∣ . For N N N sufficiently large, there exists a constant D = D ( k ) > 0 D = D(k) > 0 D = D ( k ) > 0 such that for any subset F ⊆ Γ F \subseteq\Gamma F ⊆ Γ of size at most D N ( log N ) k − 1 k D \sqrt[k]{\frac{N}{(\log N)^{k-1}}} D k ( l o g N ) k − 1 N there is a set A ⊆ Γ A \subseteq\Gamma A ⊆ Γ such that k A = Γ ∖ F kA = \Gamma\setminus F k A = Γ ∖ F .
The same result with an explicit constant was recently proven in [21 Theorem 1.3] . They stated their result for F F F of order N 1 / k / log N N^{1/k}/\log N N 1/ k / log N , but their proof also supplies N 1 / k / log ( k − 1 ) / k N N^{1/k}/\log^{(k-1)/k} N N 1/ k / log ( k − 1 ) / k N . In order to apply Theorem 6 to random Cayley graphs we need extra conditions on A A A . Firstly, we require that A A A is symmetric, so that G = Cay ( Γ , A ∖ 0 ) G = \operatorname{Cay}(\Gamma,A\setminus0) G = Cay ( Γ , A ∖ 0 ) is an undirected graph and A − A = A + A A-A=A+A A − A = A + A . Secondly, we require that 0 ∈ A 0 \in A 0 ∈ A so that G k = Cay ( Γ , k A ∖ 0 ) G^k = \operatorname{Cay}(\Gamma,kA\setminus0) G k = Cay ( Γ , k A ∖ 0 ) . Hence, we will prove a statement with slightly more conditions. A similar, but simpler, proof (without the need for orbits, Lemma 9 and exceptions for 0 0 0 ) would also prove Theorem 6 .
Theorem 7. Fix an integer k ≥ 2 k \ge2 k ≥ 2 . Let q > k q > k q > k be a prime number, Γ = ( Z / q Z ) n \Gamma= (\mathbb{Z}/q\mathbb{Z})^n Γ = ( Z / q Z ) n , and N : = ∣ Γ ∣ N := |\Gamma| N := ∣Γ∣ . For N N N sufficiently large, there exists a constant D = D ( k ) > 0 D = D(k) > 0 D = D ( k ) > 0 such that for any symmetric subset F ⊆ Γ F \subseteq\Gamma F ⊆ Γ with 0 ∉ F 0 \notin F 0 ∈ / F and of size at most D N log k − 1 N k D \sqrt[k]{\frac{N}{\log^{k-1} N}} D k l o g k − 1 N N } there is a symmetric set A ⊆ Γ A \subseteq\Gamma A ⊆ Γ with 0 ∈ A 0 \in A 0 ∈ A such that k A = Γ ∖ F kA = \Gamma\setminus F k A = Γ ∖ F .
Throughout the proof of Theorem 7 we will assume that N N N is large with respect to the fixed k k k . All asymptotic notation is henceforth with regard to N → ∞ N \to\infty N → ∞ , where the implicit constants in big O notation will depend on k k k .
The proof largely follows the same structure as the proof by Alon in [10 ] . We will show that conditioned on four likely events, the natural generalization of the random deletion process works. However, extra technicalities arise because of the symmetry, the forced inclusion of 0 0 0 and because for k > 2 k > 2 k > 2 there are distinct sets that are not disjoint, but whose sums are equal. We first give the full proof and then show that each of the “bad” events E 0 E_0 E 0 , E 1 g E_1^g E 1 g , E 2 g E_2^g E 2 g , E 3 g E_3^g E 3 g happen with negligible probability in the lemmas that follow.
Proof. Given F F F and k k k we let B B B be the set of bad multisets, i.e., those multisets of Γ \Gamma Γ of size k k k that sum to an element in F F F . For any (multi)set V ⊆ Γ V \subseteq\Gamma V ⊆ Γ we write O ( V ) O(V) O ( V ) to be the (multi)set of orbits under the inversion action, i.e. { { x , − x } : x ∈ V } \{\{x,-x\}:x \in V\} {{ x , − x } : x ∈ V } . We create a random subset C ⊆ Γ C \subseteq\Gamma C ⊆ Γ by adding orbits O ( x ) = { x , − x } O(x)=\{x,-x\} O ( x ) = { x , − x } independently with probability
p = ( a k ⋅ 2 k − 1 k ! N 1 − k ln N ) 1 / k (1) p = \left(a_k \cdot2^{k-1}k!N^{1-k}\ln N\right)^{1/k} \tag*{(1)} p = ( a k ⋅ 2 k − 1 k ! N 1 − k ln N ) 1/ k (1)
for some large enough constant a k a_k a k we determine later and adding 0 0 0 deterministically. Define B C B_C B C as the subset of B B B containing those multisets that are supported in C C C and let ⋃ B C \bigcup B_C ⋃ B C denote all 0 ≠ x ∈ Γ 0 \ne x \in\Gamma 0 = x ∈ Γ that appear in some element of B C B_C B C . We define the first bad event E 0 E_0 E 0 .
( E 0 ) (E_0) ( E 0 ) There is an element of B C B_C B C that contains both elements of a non-zero orbit. In Lemma 9 we show that E 0 E_0 E 0 holds with probability o ( 1 ) o(1) o ( 1 ) . Let E ‾ 0 \overline{E}_0 E 0 denote the complement event. Let A = C ∖ ⋃ B C A = C \setminus\bigcup B_C A = C ∖ ⋃ B C . We assumed that 0 ∉ F 0 \notin F 0 ∈ / F , so that the k k k -multiset { 0 , 0 , … , 0 } ∉ B \{0,0,\ldots,0\} \notin B { 0 , 0 , … , 0 } ∈ / B . Therefore every multiset of B B B contains some non-zero element of ⋃ B C \bigcup B_C ⋃ B C , so no multiset of B B B is supported by A A A . Additionally, F F F is symmetric, so b ∈ B C b \in B_C b ∈ B C implies − b ∈ B C -b \in B_C − b ∈ B C and hence ⋃ B C \bigcup B_C ⋃ B C is symmetric. Thus A A A is symmetric and we have defined it to contain 0 0 0 , so k A kA k A will also contain 0 0 0 . We will show that each non-zero element in Γ ∖ F \Gamma\setminus F Γ ∖ F is in k A kA k A with probability 1 − o ( 1 / N ) 1-o(1/N) 1 − o ( 1/ N ) . From this it follows by the union bound that k A = Γ ∖ F kA=\Gamma\setminus F k A = Γ ∖ F with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) and hence there is at least one such A A A .
We say that a (multi)set of orbits sums to h h h if we can choose an element of each orbit in the set such that the sum of those elements is h h h .
Fix a non-zero element g ∈ Γ ∖ F g \in\Gamma\setminus F g ∈ Γ ∖ F . We define the bad event E 1 g E_1^g E 1 g as follows:
( E 1 g ) (E_1^g) ( E 1 g ) there is no set of disjoint k k k -sets of C C C that sum to g g g of size 2 ln N 2\ln N 2 ln N .
Suppose E 1 g E_1^g E 1 g fails and let C g C_g C g be a family of 2 ln N 2\ln N 2 ln N disjoint k k k -sets of orbits summing to g g g . If g ∉ k A g \notin kA g ∈ / k A each set in C g C_g C g needs to intersect a set in B C B_C B C . Consider pairs ( b , c ) ∈ B C × C g (b,c)\in B_C\times C_g ( b , c ) ∈ B C × C g such that O ( b ) ∩ c ≠ ∅ \mathcal{O}(b)\cap c\ne\varnothing O ( b ) ∩ c = ∅ . We will say that this is a blocking pair or b b b blocks c c c . In writing down all blocking pairs each b b b can appear at most k k k times, because b b b contains at most k k k different elements and all c ∈ C g c\in C_g c ∈ C g have disjoint orbits. Thus we can greedily pick a sequence S S S of 2 k ln N \frac{2}{k}\ln N k 2 ln N blocking pairs ( b i , c i ) (b_i,c_i) ( b i , c i ) such that O ( b i ) ∩ c j = ∅ \mathcal{O}(b_i)\cap c_j=\varnothing O ( b i ) ∩ c j = ∅ if i < j i<j i < j (at each step we delete all c j c_j c j that are blocked by the chosen b i b_i b i ). Now consider the next bad event E 2 g E_2^g E 2 g :
( E 2 g ) (E_2^g) ( E 2 g ) there is { − x , x } ∈ Γ \{-x,x\}\in\Gamma { − x , x } ∈ Γ (with x = 0 x=0 x = 0 possible), a sequence of b 1 , … , b k + 2 ∈ B C b_1,\ldots,b_{k+2}\in B_C b 1 , … , b k + 2 ∈ B C and distinct c 1 , … , c k + 2 ∈ C g c_1,\ldots,c_{k+2}\in C_g c 1 , … , c k + 2 ∈ C g such that all b i b_i b i contain x x x or − x -x − x but none of the c i c_i c i contain { − x , x } \{-x,x\} { − x , x } , b i b_i b i blocks c i c_i c i and O ( b i ) ∩ c j = ∅ \mathcal{O}(b_i)\cap c_j=\varnothing O ( b i ) ∩ c j = ∅ for i < j i<j i < j .
Suppose that E 2 g E_2^g E 2 g fails. For any ( b i , c i ) ∈ S (b_i,c_i)\in S ( b i , c i ) ∈ S and x ∈ b i x\in b_i x ∈ b i there are at most k + 1 k+1 k + 1 other ( b j , c j ) ∈ S (b_j,c_j)\in S ( b j , c j ) ∈ S with x ∈ b j x\in b_j x ∈ b j or in one of the orbits of c j c_j c j , because including ( b i , c i ) (b_i,c_i) ( b i , c i ) there are at most k + 2 k+2 k + 2 : at most one where an orbit of c j c_j c j contains x x x and at most k + 1 k+1 k + 1 more due to the failure of E 2 g E_2^g E 2 g . By definition of S S S any ( b i , c i ) (b_i,c_i) ( b i , c i ) can intersect at most ( k + 1 ) k (k+1)k ( k + 1 ) k ( b j , c j ) ∈ S (b_j,c_j)\in S ( b j , c j ) ∈ S with j < i j<i j < i . If g ∉ k A g\notin kA g ∈ / k A , then there must be 2 k ( k ( k + 1 ) + 1 ) ln N \frac{2}{k(k(k+1)+1)}\ln N k ( k ( k + 1 ) + 1 ) 2 ln N pairs of ( b i , c i ) ∈ S (b_i,c_i)\in S ( b i , c i ) ∈ S that are completely disjoint from each other. This implies the third bad event E 3 g E_3^g E 3 g :
( E 3 g ) (E_3^g) ( E 3 g ) there are 2 k 2 ( k + 2 ) ln N \frac{2}{k^2(k+2)}\ln N k 2 ( k + 2 ) 2 ln N disjoint blocking pairs ( b i , c i ) ∈ B C × C g (b_i,c_i)\in B_C\times C_g ( b i , c i ) ∈ B C × C g .
We have deduced that if E 0 E_0 E 0 , E 1 g E_1^g E 1 g , E 2 g E_2^g E 2 g and E 3 g E_3^g E 3 g all fail, then g ∈ k A g\in kA g ∈ k A . In particular, by the union bound
P ( k A ≠ Γ ∖ F ) ≤ P ( E 0 ) + ∑ 0 ≠ g ∈ Γ ∖ F [ P ( E 1 g ) + P ( E 2 g ∩ E ‾ 0 ) + P ( E 3 g ∩ E ‾ 0 ) ] . \mathbb{P}(kA\ne\Gamma\setminus F)\le\mathbb{P}(E_0)+\sum_{0\ne g\in\Gamma\setminus F}\left[\mathbb{P}(E_1^g)+\mathbb{P}(E_2^g\cap\overline{E}_0)+\mathbb{P}(E_3^g\cap\overline{E}_0)\right]. P ( k A = Γ ∖ F ) ≤ P ( E 0 ) + 0 = g ∈ Γ ∖ F ∑ [ P ( E 1 g ) + P ( E 2 g ∩ E 0 ) + P ( E 3 g ∩ E 0 ) ] .
For every non-zero g ∈ Γ ∖ F g\in\Gamma\setminus F g ∈ Γ ∖ F each of the events E 1 g E_1^g E 1 g , E 2 g ∩ E ‾ 0 E_2^g\cap\overline{E}_0 E 2 g ∩ E 0 , E 3 g ∩ E ‾ 0 E_3^g\cap\overline{E}_0 E 3 g ∩ E 0 occurs with probability o ( 1 / N ) o(1/N) o ( 1/ N ) by Lemmas 8 , 11 and 12 respectively. Hence the sum is o ( 1 ) o(1) o ( 1 ) and thus P ( k A = Γ ∖ F ) = 1 − o ( 1 ) \mathbb{P}(kA=\Gamma\setminus F)=1-o(1) P ( k A = Γ ∖ F ) = 1 − o ( 1 ) .
We now prove that the events hold with appropriately small probability in the order E 1 g E_1^g E 1 g , E 0 E_0 E 0 , E 2 g E_2^g E 2 g , E 3 g E_3^g E 3 g (for 0 ≠ g ∈ Γ ∖ F 0\ne g\in\Gamma\setminus F 0 = g ∈ Γ ∖ F ).
Lemma 8. Let E 1 g E_1^g E 1 g be the event that there are fewer than 2 ln N 2\ln N 2 ln N pairwise disjoint sets of k k k orbits in C C C that sum to g g g . Then P ( E 1 g ) = o ( 1 / N ) \mathbb{P}(E_1^g)=o(1/N) P ( E 1 g ) = o ( 1/ N ) .
Proof. Note that g ≠ 0 g \ne0 g = 0 . Let S g \mathcal{S}_g S g be the family of k k k -sets of orbits (excluding the orbit { 0 } \{0\} { 0 } ) that sum to g g g . Recall that this means that we can pick one element from each orbit so that the elements sum to g g g . Let C g g \mathcal{C}^{g}_g C g g be the subset of S g \mathcal{S}_g S g which only contains sets that are fully inside C \mathcal{C} C . We will show that the set C g g \mathcal{C}^{g}_g C g g contains a family of disjoint sets of size s = 2 ln N s=2\ln N s = 2 ln N with probability 1 − o ( 1 / N ) 1-o(1/N) 1 − o ( 1/ N ) .
Let s = 2 ln N s=2\ln N s = 2 ln N . Let M \mathcal{M} M denote a maximal family of disjoint sets in C g g \mathcal{C}^{g}_g C g g and let M = ∣ M ∣ M=|\mathcal{M}| M = ∣ M ∣ . We will show that P ( M < s ) = o ( 1 / N ) \mathbb{P}(M<s)=o(1/N) P ( M < s ) = o ( 1/ N ) . Let U = ⋃ c ∈ M c U=\bigcup_{c\in\mathcal{M}}c U = ⋃ c ∈ M c be the set of all orbits that are in one of the elements of M \mathcal{M} M . If M < s M<s M < s , then there are k M < k s kM<ks k M < k s orbits in U U U . If there is a set in C g g \mathcal{C}^{g}_g C g g disjoint from U U U , then we can add it to the family, contradicting the maximality of M \mathcal{M} M . For any subset S ⊆ Γ S\subseteq\Gamma S ⊆ Γ let X S X_S X S denote the number of sets in C g g \mathcal{C}^{g}_g C g g that are disjoint from S S S . The set U U U satisfies the events that X U = 0 X_U=0 X U = 0 and that U ⊆ O ( C ) U\subseteq\mathcal{O}(\mathcal{C}) U ⊆ O ( C ) . These events are independent, as they depend on disjoint elements to be included in C \mathcal{C} C . Therefore we find that
P ( M < s ) ≤ ∑ i = 0 s − 1 ∑ U ⊆ O ( Γ ) , ∣ U ∣ = k i , union of disjoint orbits in S g P ( X U = 0 ) P ( U ⊆ O ( C ) ) . \mathbb{P}(M<s)\leq\sum_{i=0}^{s-1}\ \sum_{\substack{U\subseteq\mathcal{O}(\Gamma),\ |U|=ki,\\ \text{union of disjoint orbits in }\mathcal{S}_g}}\mathbb{P}(X_U=0)\mathbb{P}(U\subseteq\mathcal{O}(\mathcal{C})). P ( M < s ) ≤ i = 0 ∑ s − 1 U ⊆ O ( Γ ) , ∣ U ∣ = k i , union of disjoint orbits in S g ∑ P ( X U = 0 ) P ( U ⊆ O ( C )) .
It is immediate to see that P ( U ⊆ O ( C ) ) = p k i \mathbb{P}(U\subseteq\mathcal{O}(\mathcal{C}))=p^{ki} P ( U ⊆ O ( C )) = p k i . In estimating P ( X U = 0 ) \mathbb{P}(X_U=0) P ( X U = 0 ) we first count the number of sets in S g \mathcal{S}_g S g that are disjoint from U U U , denoted by S g U \mathcal{S}^{U}_g S g U . Given k − 1 k-1 k − 1 orbits of S ∈ S g S\in\mathcal{S}_g S ∈ S g that are outside U U U there is at least one choice of the final element (and hence final orbit) to make the set of orbits sum to g g g . This overcounts the total amount by a factor k k k , once for each final orbit added. There are N − 1 2 \frac{N-1}{2} 2 N − 1 orbits to choose from in total, so this suggests that there are at least 1 k ( ( N − 1 ) / 2 − ∣ U ∣ k − 1 ) \frac{1}{k}\binom{(N-1)/2-|U|}{k-1} k 1 ( k − 1 ( N − 1 ) /2 − ∣ U ∣ ) such sets. If the last orbit is not zero, outside U U U and distinct from the first k − 1 k-1 k − 1 orbits, then this indeed gives a set in S g U \mathcal{S}^{U}_g S g U . The number of cases where the last element fails to satisfy those conditions is O ( N k − 2 ( ∣ U ∣ + k ) ) O(N^{k-2}(|U|+k)) O ( N k − 2 ( ∣ U ∣ + k )) , which is o ( 1 ) o(1) o ( 1 ) of all cases because ∣ U ∣ < 2 k ln N |U|<2k\ln N ∣ U ∣ < 2 k ln N . Hence the number of sets in S g U \mathcal{S}^{U}_g S g U is at least N k − 1 2 k − 1 k ! ( 1 − o ( 1 ) ) \frac{N^{k-1}}{2^{k-1}k!}(1-o(1)) 2 k − 1 k ! N k − 1 ( 1 − o ( 1 )) . Hence the expected size of C g U = S g U ∩ ( C k ) \mathcal{C}^{U}_g=\mathcal{S}^{U}_g\cap\binom{\mathcal{C}}{k} C g U = S g U ∩ ( k C ) is
μ U ≥ N k − 1 2 k − 1 k ! ( 1 − o ( 1 ) ) p k = ( a k − o ( 1 ) ) ln N . \mu_U\geq\frac{N^{k-1}}{2^{k-1}k!}(1-o(1))p^k=(a_k-o(1))\ln N. μ U ≥ 2 k − 1 k ! N k − 1 ( 1 − o ( 1 )) p k = ( a k − o ( 1 )) ln N .
To apply Janson’s inequality, specifically P ( X U = 0 ) ≤ exp ( − μ U + Δ / 2 ) \mathbb{P}(X_U=0)\leq\exp(-\mu_U+\Delta/2) P ( X U = 0 ) ≤ exp ( − μ U + Δ/2 ) , we estimate
Δ = ∑ c , c ′ ∈ S g U distinct c ∩ c ′ ≠ ∅ P ( c , c ′ ∈ C g U ) . \Delta=\sum_{\substack{c,c'\in\mathcal{S}^{U}_g\text{ distinct}\\c\cap c'\ne\varnothing}}\mathbb{P}(c,c'\in\mathcal{C}^{U}_g). Δ = c , c ′ ∈ S g U distinct c ∩ c ′ = ∅ ∑ P ( c , c ′ ∈ C g U ) .
The sets of orbits c c c and c ′ c' c ′ sum to g g g and are distinct. They can intersect in at most k − 1 k-1 k − 1 elements. Suppose c , c ′ c,c' c , c ′ intersect in i i i orbits. There are at most 2 k − 1 ( ( N − 1 ) / 2 k − 1 ) 2^{k-1}\binom{(N-1)/2}{k-1} 2 k − 1 ( k − 1 ( N − 1 ) /2 ) sets in S g U \mathcal{S}^{U}_g S g U , because fixing k − 1 k-1 k − 1 orbits gives at most 2 k − 1 2^{k-1} 2 k − 1 final elements which give sum g g g for some choice of representative per orbit. Given c c c there are ( k i ) \binom{k}{i} ( i k ) ways to choose orbits of c ′ c' c ′ in the intersections. Choosing k − 1 − i k-1-i k − 1 − i other elements leaves at most 2 k − 1 2^{k-1} 2 k − 1 choices for the last element. Hence we can choose at most 2 k − 1 ( k i ) ( ( N − 1 ) / 2 − k k − i − 1 ) 2^{k-1}\binom{k}{i}\binom{(N-1)/2-k}{k-i-1} 2 k − 1 ( i k ) ( k − i − 1 ( N − 1 ) /2 − k ) sets c ′ ∈ C g U c'\in\mathcal{C}^{U}_g c ′ ∈ C g U that intersect c c c in i i i orbits for all 1 ≤ i ≤ k − 1 1 \le i \le k-1 1 ≤ i ≤ k − 1 . Hence we bound
Δ ≤ ∑ c ∈ S g U ∑ i = 1 k − 1 2 k − 1 ( k i ) ( ( N − 1 ) / 2 k − 1 − i ) p 2 k − i ≤ 2 k − 1 ( ( N − 1 ) / 2 k − 1 ) ∑ i = 1 k − 1 2 k − 1 ( k i ) ( ( N − 1 ) / 2 k − 1 − i ) p 2 k − i = ∑ i = 1 k − 1 O ( N 2 k − 2 − i ( N 1 − k ln N ) 2 − i / k ) = o ( ln N ) , \begin{aligned}
\Delta\le\sum_{c \in\mathcal{S}_g^U} \sum_{i=1}^{k-1} 2^{k-1} \binom{k}{i} \binom{(N-1)/2}{k-1-i} p^{2k-i} \le2^{k-1} \binom{(N-1)/2}{k-1} \sum_{i=1}^{k-1} 2^{k-1} \binom{k}{i} \binom{(N-1)/2}{k-1-i} p^{2k-i} \\
&= \sum_{i=1}^{k-1} O(N^{2k-2-i}(N^{1-k}\ln N)^{2-i/k}) = o(\ln N),
\end{aligned} Δ ≤ c ∈ S g U ∑ i = 1 ∑ k − 1 2 k − 1 ( i k ) ( k − 1 − i ( N − 1 ) /2 ) p 2 k − i ≤ 2 k − 1 ( k − 1 ( N − 1 ) /2 ) i = 1 ∑ k − 1 2 k − 1 ( i k ) ( k − 1 − i ( N − 1 ) /2 ) p 2 k − i = i = 1 ∑ k − 1 O ( N 2 k − 2 − i ( N 1 − k ln N ) 2 − i / k ) = o ( ln N ) ,
so by Janson’s inequality we have
P ( X U = 0 ) ≤ exp ( − μ U + Δ / 2 ) ≤ exp ( − a k ln N + o ( ln N ) ) ≤ N − a k + o ( 1 ) . \mathbb{P}(X_U=0) \le\exp(-\mu_U+\Delta/2) \le\exp(-a_k\ln N+o(\ln N)) \le N^{-a_k+o(1)}. P ( X U = 0 ) ≤ exp ( − μ U + Δ/2 ) ≤ exp ( − a k ln N + o ( ln N )) ≤ N − a k + o ( 1 ) .
The number of sets U U U of size k i ki k i that can arise as a union of disjoint sets in S g \mathcal{S}_g S g is at most ( ∣ S g ∣ i ) ≤ ( e ∣ S g ∣ / i i ) ≤ ( e N k − 1 / k ! i ) \binom{|\mathcal{S}_g|}{i} \le\binom{e|\mathcal{S}_g|/i}{i} \le\binom{eN^{k-1}/k!}{i} ( i ∣ S g ∣ ) ≤ ( i e ∣ S g ∣/ i ) ≤ ( i e N k − 1 / k ! ) , because ∣ S g ∣ ≤ N k − 1 k ! ( 1 − o ( 1 ) ) |\mathcal{S}_g| \le\frac{N^{k-1}}{k!}(1-o(1)) ∣ S g ∣ ≤ k ! N k − 1 ( 1 − o ( 1 )) . Hence
P ( M < s ) ≤ ∑ i = 0 s − 1 ( e N k − 1 / k ! i ) i p k i N − a k + o ( 1 ) ≤ s ( e N k − 1 p k s ⋅ k ! ) s N − a k + o ( 1 ) = s ( e 2 k − 2 a k ) 2 ln N N − a k + o ( 1 ) = o ( 1 / N ) , \begin{aligned}
\mathbb{P}(M<s) \le\sum_{i=0}^{s-1} \left(\frac{eN^{k-1}/k!}{i}\right)^i p^{ki}N^{-a_k+o(1)} \\
&\le s\left(\frac{eN^{k-1}p^k}{s\cdot k!}\right)^s N^{-a_k+o(1)} \\
&= s(e2^{k-2}a_k)^{2\ln N}N^{-a_k+o(1)} \\
&= o(1/N),
\end{aligned} P ( M < s ) ≤ i = 0 ∑ s − 1 ( i e N k − 1 / k ! ) i p k i N − a k + o ( 1 ) ≤ s ( s ⋅ k ! e N k − 1 p k ) s N − a k + o ( 1 ) = s ( e 2 k − 2 a k ) 2 l n N N − a k + o ( 1 ) = o ( 1/ N ) ,
where a k a_k a k is chosen large enough that this final equality holds. Here we used that ( e N k − 1 p k i ⋅ k ! ) i \left(\frac{eN^{k-1}p^k}{i\cdot k!}\right)^i ( i ⋅ k ! e N k − 1 p k ) i is increasing in i i i when i ≤ N k − 1 p k k ! i \le\frac{N^{k-1}p^k}{k!} i ≤ k ! N k − 1 p k which is bigger than 2 ln N 2\ln N 2 ln N by definition of p p p , see (1) .
We conclude that the set C g ′ C'_g C g ′ contains a family of disjoint sets of size s = 2 ln N s=2\ln N s = 2 ln N with probability 1 − o ( 1 / N ) 1-o(1/N) 1 − o ( 1/ N ) .
Before we move to the next lemma, we make the following observation. Consider a k k k -multiset b b b with all distinct elements fixed except one, which we give the variable x x x and x x x occurs t t t times in b b b . We know that the sum of the elements of b b b is t x + h tx+h t x + h for some h ∈ Γ h \in\Gamma h ∈ Γ . We know that t ≤ k t \le k t ≤ k , so gcd ( t , q ) = 1 \gcd(t,q)=1 g cd( t , q ) = 1 and thus there are exactly ∣ F ∣ |F| ∣ F ∣ choices for x x x such that t x + h ∈ F tx+h \in F t x + h ∈ F .
Lemma 9. Let E 0 E_0 E 0 be the event that there is a multiset b ∈ B C b \in B_C b ∈ B C that contains { x , − x } \{x,-x\} { x , − x } for some non-zero x x x . Then P ( E 0 ) = o ( 1 ) \mathbb{P}(E_0)=o(1) P ( E 0 ) = o ( 1 ) .
Proof. Each full orbit sums to zero, so in case k = 2 k=2 k = 2 there are no sets containing { x , − x } \{x,-x\} { x , − x } in B B B . Assume k ≥ 3 k \ge3 k ≥ 3 . If a multiset b ∈ B C b \in B_C b ∈ B C contains a full non-zero orbit, then there must be a submultiset b ′ ⊆ b b' \subseteq b b ′ ⊆ b without full orbits (also without { 0 } \{0\} { 0 } ) of size at most k − 2 ≥ 1 k-2 \ge1 k − 2 ≥ 1 that sums to an element in F F F . Let X t X_t X t be the number of multisubsets of size t t t of elements of orbits in C C C containing no full orbits (including zero) and summing to an element in F F F . Suppose b ′ b' b ′ of size t t t contains no full orbits and contains i i i different elements of Γ \Gamma Γ . Then P ( O ( b ′ ) ⊆ C ) = p i \mathbb{P}(O(b') \subseteq C)=p^i P ( O ( b ′ ) ⊆ C ) = p i , because none of the elements lie in the same orbit and none are zero. There are at most O ( 1 ) ( n i − 1 ) ∣ F ∣ O(1)\binom{n}{i-1}|F| O ( 1 ) ( i − 1 n ) ∣ F ∣ such b ′ b' b ′ , because there are at most t i t^i t i ways to decide the multiplicities of the i i i distinct elements and given those multiplicities choosing the first i − 1 i-1 i − 1 elements leave at most ∣ F ∣ |F| ∣ F ∣ options for the final one, by the remark above. Therefore, the expected number of X t X_t X t is
E ( X t ) = ∑ i = 1 t O ( 1 ) N i − 1 ∣ F ∣ p i = O ~ ( ∑ i = 1 t N ( i + 1 ) / k − 1 ) = O ~ k ( N ( t + 1 − k ) / k ) . \mathbb{E}(X_t)=\sum_{i=1}^{t}O(1)N^{i-1}|F|p^i=\widetilde{O}\left(\sum_{i=1}^{t}N^{(i+1)/k-1}\right)=\widetilde{O}_k\left(N^{(t+1-k)/k}\right). E ( X t ) = i = 1 ∑ t O ( 1 ) N i − 1 ∣ F ∣ p i = O ( i = 1 ∑ t N ( i + 1 ) / k − 1 ) = O k ( N ( t + 1 − k ) / k ) .
As t ≤ k − 2 t\leq k-2 t ≤ k − 2 all these expected values go to zero and the probability that there is one such set also goes to zero by Markov’s inequality.
In the remaining Lemmas we will count the number of blocking pairs given that the elements of b b b come from a fixed set. We record this count here as a separate lemma.
Lemma 10. Consider the subset B ′ ⊆ B B'\subseteq B B ′ ⊆ B of multisets that contain no non-zero { − x , x } \{-x,x\} { − x , x } and let S ⊆ Γ S\subseteq\Gamma S ⊆ Γ be a fixed set of size s s s . The number of blocking pairs ( b , c ) ∈ B ′ × S g (b,c)\in B'\times S_g ( b , c ) ∈ B ′ × S g with the elements of b b b either in S S S or one of the orbits of c c c is O ( ∣ F ∣ ( N k − 2 ) ) O\left(|F|\binom{N}{k-2}\right) O ( ∣ F ∣ ( k − 2 N ) ) where the implied constant only depends on s s s and k k k .
Proof. Let z 1 , … , z k z_1,\ldots,z_k z 1 , … , z k be variables that denote the elements of the orbits of c c c that sum to g g g . Without loss of generality let z 1 z_1 z 1 be the variable such that { z 1 , − z 1 } ∈ O ( b ) \{z_1,-z_1\}\in O(b) { z 1 , − z 1 } ∈ O ( b ) , which exists because b b b blocks c c c . If z 1 ∈ b z_1\in b z 1 ∈ b , then, because g ∉ F g\notin F g ∈ / F , there is a z i z_i z i that will not appear in b b b . Similarly if − z 1 ∈ b -z_1\in b − z 1 ∈ b , then there is a − z i -z_i − z i that does not appear in b b b , because − g ∉ F -g\notin F − g ∈ / F . Without loss of generality take i = 2 i=2 i = 2 . There are at most ( N k − 2 ) \binom{N}{k-2} ( k − 2 N ) ways to choose z 3 , … , z k z_3,\ldots,z_k z 3 , … , z k (less because they all need to be in distinct orbits). Leaving z 1 , z 2 z_1,z_2 z 1 , z 2 as variables there are at most ( s + 2 k ) k (s+2k)^k ( s + 2 k ) k ways to decide on the values of b ∖ { z 1 , − z 1 , z 2 , − z 2 } b\setminus\{z_1,-z_1,z_2,-z_2\} b ∖ { z 1 , − z 1 , z 2 , − z 2 } and the multiplicities of the ± z 1 , ± z 2 \pm z_1,\pm z_2 ± z 1 , ± z 2 that appear. Note that at most one of z 1 , − z 1 z_1,-z_1 z 1 , − z 1 appears in b b b , because b ⊆ B ′ b\subseteq B' b ⊆ B ′ . Let the multiplicity of z 1 z_1 z 1 be t 1 t_1 t 1 (where t 1 < 0 t_1<0 t 1 < 0 if − z 1 ∈ b -z_1\in b − z 1 ∈ b ). Similarly at most one of z 2 , − z 2 z_2,-z_2 z 2 , − z 2 appears and let t 2 t_2 t 2 be the (signed) multiplicity of z 2 z_2 z 2 . Let a = z 3 + ⋯ + z k a=z_3+\cdots+z_k a = z 3 + ⋯ + z k and let a ′ a' a ′ be the sum of the remaining elements in b b b , then the conditions on c c c and b b b imply that
( 1 1 t 1 t 2 ) ( z 1 z 2 ) = ( g − a f − a ′ ) \begin{pmatrix}1&1\\t_1&t_2\end{pmatrix}
\begin{pmatrix}z_1\\z_2\end{pmatrix}
=
\begin{pmatrix}g-a\\f-a'\end{pmatrix} ( 1 t 1 1 t 2 ) ( z 1 z 2 ) = ( g − a f − a ′ )
where f ∈ F f\in F f ∈ F . We know that ∣ t 1 ∣ + ∣ t 2 ∣ ≤ k < q |t_1|+|t_2|\leq k<q ∣ t 1 ∣ + ∣ t 2 ∣ ≤ k < q and that t 1 , t 2 t_1,t_2 t 1 , t 2 do not have the same sign (note that t 2 t_2 t 2 can be zero). Hence the matrix has rank 2 2 2 and for each f ∈ F f\in F f ∈ F there is exactly one solution. We conclude that there are O ( ∣ F ∣ ( N k − 2 ) ) O\left(|F|\binom{N}{k-2}\right) O ( ∣ F ∣ ( k − 2 N ) ) blocking pairs.
Lemma 11. Let E 2 g E^g_2 E 2 g be the event that there is some orbit { x , − x } ⊆ Γ \{x,-x\}\subseteq\Gamma { x , − x } ⊆ Γ and m = k + 2 m=k+2 m = k + 2 multisets b 1 , … , b m ∈ B C b_1,\ldots,b_m\in B_C b 1 , … , b m ∈ B C and sets of orbits c 1 , … , c m ∈ C g c_1,\ldots,c_m\in C_g c 1 , … , c m ∈ C g such that for all i i i we have { x , − x } ∈ O ( b i ) ∖ c i \{x,-x\}\in O(b_i)\setminus c_i { x , − x } ∈ O ( b i ) ∖ c i , b i b_i b i blocks c i c_i c i , and O ( b i ) ∩ c j = ∅ O(b_i)\cap c_j=\varnothing O ( b i ) ∩ c j = ∅ for i < j i<j i < j . Then P ( E 2 g ∖ E 0 ) = o ( 1 / N ) \mathbb{P}(E^g_2\setminus E_0)=o(1/N) P ( E 2 g ∖ E 0 ) = o ( 1/ N ) .
Proof. We estimate the expected number of tuples without assuming that the c i c_i c i are within C g C_g C g , i.e., satisfying the slightly looser conditions: x , b 1 , … , b m , c 1 , … , c m x,b_1,\ldots,b_m,c_1,\ldots,c_m x , b 1 , … , b m , c 1 , … , c m where E 0 E_0 E 0 does not hold, b i ∈ B C b_i\in B_C b i ∈ B C blocks c i ∈ ( Γ k ) c_i\in\binom{\Gamma}{k} c i ∈ ( k Γ ) , { x , − x } ∈ O ( b i ) ∖ c i \{x,-x\}\in O(b_i)\setminus c_i { x , − x } ∈ O ( b i ) ∖ c i for all i i i , the c i c_i c i are disjoint and sum to g g g , and O ( b i ) ∩ c j = ∅ O(b_i)\cap c_j=\varnothing O ( b i ) ∩ c j = ∅ if i < j i<j i < j .
First, we upper bound the number of such tuples with b i ∈ B b_i\in B b i ∈ B and c i ∈ S g c_i\in S_g c i ∈ S g . Suppose that the total number of elements in the set L = ⋃ i = 1 m O ( b i ) ∖ ⋃ i = 1 m c i L=\bigcup_{i=1}^m O(b_i)\setminus\bigcup_{i=1}^m c_i L = ⋃ i = 1 m O ( b i ) ∖ ⋃ i = 1 m c i is ℓ \ell ℓ . Then ℓ ≤ m ( k − 2 ) + 1 \ell\leq m(k-2)+1 ℓ ≤ m ( k − 2 ) + 1 because each O ( b i ) O(b_i) O ( b i ) contains { x , − x } \{x,-x\} { x , − x } and at least one element of c i c_i c i . There are at most ( N ℓ ) \binom{N}{\ell} ( ℓ N ) choices for the ℓ \ell ℓ orbits and O ( x ) O(x) O ( x ) must be chosen among those, so there are ℓ \ell ℓ choices for O ( x ) \mathcal{O}(x) O ( x ) . In determining the number of possible tuples we fix the elements of ( b i , c i ) (b_i,c_i) ( b i , c i ) in increasing order of i i i . Having determined ( b j , c j ) (b_j,c_j) ( b j , c j ) for all j < i j<i j < i we know that the elements of b i b_i b i are among the elements in L ∪ ⋃ j < i c j L\cup\bigcup_{j<i}c_j L ∪ ⋃ j < i c j , a set of size less than 2 ( ℓ + k i ) = O ( 1 ) 2(\ell+ki)=O(1) 2 ( ℓ + k i ) = O ( 1 ) , so by Lemma 10 we get at most O ( ∣ F ∣ ( N k − 2 ) ) O\left(|F| \binom{N}{k-2}\right) O ( ∣ F ∣ ( k − 2 N ) ) options for ( b i , c i ) (b_i,c_i) ( b i , c i ) . We can conclude that the number of tuples we consider is at most O ( ( N ℓ ) ℓ ∣ F ∣ m ∏ i = 1 m ( N k − 2 ) ∣ F ∣ ) O\left(\binom{N}{\ell}\ell|F|^m\prod_{i=1}^m\binom{N}{k-2}|F|\right) O ( ( ℓ N ) ℓ ∣ F ∣ m ∏ i = 1 m ( k − 2 N ) ∣ F ∣ ) . Among these there are O ( ( N ℓ − 1 ) ℓ ∏ i = 1 m ( N k − 2 ) ( ℓ + i k ) k − 2 ∣ F ∣ ) O\left(\binom{N}{\ell-1}\ell\prod_{i=1}^m\binom{N}{k-2}(\ell+ik)^{k-2}|F|\right) O ( ( ℓ − 1 N ) ℓ ∏ i = 1 m ( k − 2 N ) ( ℓ + ik ) k − 2 ∣ F ∣ ) sets with 0 ∈ L 0\in L 0 ∈ L . In total there are at least m k + ℓ mk+\ell mk + ℓ disjoint orbits in ⋃ i = 1 m O ( b i ) ∪ ⋃ i = 1 m c i \bigcup_{i=1}^m\mathcal{O}(b_i)\cup\bigcup_{i=1}^m c_i ⋃ i = 1 m O ( b i ) ∪ ⋃ i = 1 m c i , because all the c i c_i c i are pairwise disjoint. The probability that a tuple is included is p m k + ℓ p^{mk+\ell} p mk + ℓ or p m k + ℓ − 1 p^{mk+\ell-1} p mk + ℓ − 1 in case { 0 } ∈ L \{0\}\in L { 0 } ∈ L . The case with { 0 } ∉ L \{0\}\notin L { 0 } ∈ / L has a factor N p = ω ( 1 ) Np=\omega(1) N p = ω ( 1 ) more and is therefore the dominating term. Hence the expected number of such tuples is at most
O ( N ℓ ∣ F ∣ m ( N k − 2 ) m p m k + ℓ ) = O ~ ( N ℓ + m / k + m ( k − 2 ) − m ( k − 1 ) − ℓ + ℓ / k ) = O ~ k ( N ( m + ℓ ) / k − m ) = o ( 1 / N ) O\left(N^\ell|F|^m\binom{N}{k-2}^m p^{mk+\ell}\right)=\widetilde{O}\left(N^{\ell+m/k+m(k-2)-m(k-1)-\ell+\ell/k}\right)
=\widetilde{O}_k\left(N^{(m+\ell)/k-m}\right)=o(1/N) O ( N ℓ ∣ F ∣ m ( k − 2 N ) m p mk + ℓ ) = O ( N ℓ + m / k + m ( k − 2 ) − m ( k − 1 ) − ℓ + ℓ / k ) = O k ( N ( m + ℓ ) / k − m ) = o ( 1/ N )
because m = k + 2 m=k+2 m = k + 2 and ℓ ≤ m ( k − 2 ) + 1 \ell\le m(k-2)+1 ℓ ≤ m ( k − 2 ) + 1 . By Markov’s inequality we conclude that P ( E 3 g ∖ E 0 ) = o ( 1 / N ) \mathbb{P}(E_3^g\setminus E_0)=o(1/N) P ( E 3 g ∖ E 0 ) = o ( 1/ N ) .
Lemma 12. Let E 3 g E_3^g E 3 g be the event that there are 2 k 2 ( k + 2 ) ln N \frac{2}{k^2(k+2)}\ln N k 2 ( k + 2 ) 2 ln N disjoint blocking pairs ( b i , c i ) ∈ B C × C g (b_i,c_i)\in B_C\times C_g ( b i , c i ) ∈ B C × C g . Then, P ( E 3 g ∖ E 0 ) = o ( 1 / N ) \mathbb{P}(E_3^g\setminus E_0)=o(1/N) P ( E 3 g ∖ E 0 ) = o ( 1/ N ) .
Proof. We only need to calculate the probability when none of the b i b_i b i contain both elements of a non-zero orbit. For each k ≤ ℓ ≤ 2 k − 2 k\le\ell\le2k-2 k ≤ ℓ ≤ 2 k − 2 define A ℓ A_\ell A ℓ to be the event that there are at least k + 1 k+1 k + 1 disjoint blocking pairs ( b , c ) (b,c) ( b , c ) such that as a set ∣ O ( b ) ∪ c ∣ = ℓ |\mathcal{O}(b)\cup c|=\ell ∣ O ( b ) ∪ c ∣ = ℓ for every pair. Define A 2 k − 1 A_{2k-1} A 2 k − 1 to be the similar event that there are at least s : = 1 k 2 ( k + 2 ) ln N s:=\frac{1}{k^2(k+2)}\ln N s := k 2 ( k + 2 ) 1 ln N disjoint blocking pairs ( b , c ) (b,c) ( b , c ) with ∣ O ( b ) ∪ c ∣ = 2 k − 1 |\mathcal{O}(b)\cup c|=2k-1 ∣ O ( b ) ∪ c ∣ = 2 k − 1 for every pair. In order to show that P ( E 3 g ) = o ( 1 / N ) \mathbb{P}(E_3^g)=o(1/N) P ( E 3 g ) = o ( 1/ N ) , it suffices to show that P ( A ℓ ) = o ( 1 / N ) \mathbb{P}(A_\ell)=o(1/N) P ( A ℓ ) = o ( 1/ N ) for all k ≤ ℓ ≤ 2 k − 1 k\le\ell\le2k-1 k ≤ ℓ ≤ 2 k − 1 as long as k ( k − 1 ) + s ≤ 2 k 2 ( k + 2 ) ln N k(k-1)+s\le\frac{2}{k^2(k+2)}\ln N k ( k − 1 ) + s ≤ k 2 ( k + 2 ) 2 ln N , which is clearly satisfied for large enough N N N .
So consider for each k ≤ ℓ ≤ 2 k − 1 k\le\ell\le2k-1 k ≤ ℓ ≤ 2 k − 1 the pairs ( b , c ) ∈ B × S g (b,c)\in B\times S_g ( b , c ) ∈ B × S g for which ∣ O ( b ) ∪ c ∣ = ℓ |\mathcal{O}(b)\cup c|=\ell ∣ O ( b ) ∪ c ∣ = ℓ . There are at most ( ( N + 1 ) / 2 ℓ − k ) \binom{(N+1)/2}{\ell-k} ( ℓ − k ( N + 1 ) /2 ) ways to choose the ℓ − k \ell-k ℓ − k orbits that are not in c c c . Given those, b b b must take its elements among at most 2 ( ℓ − k ) 2(\ell-k) 2 ( ℓ − k ) elements in these orbits and the elements in c c c , so by Lemma 10 there are O ( ( N ℓ − k ) ( N k − 2 ) ∣ F ∣ ) O\left(\binom{N}{\ell-k}\binom{N}{k-2}|F|\right) O ( ( ℓ − k N ) ( k − 2 N ) ∣ F ∣ ) blocking pairs with ∣ O ( b ) ∪ c ∣ = ℓ |\mathcal{O}(b)\cup c|=\ell ∣ O ( b ) ∪ c ∣ = ℓ . Hence there are at most O ( ( N ℓ − 2 ∣ F ∣ t ) ) O\left(\binom{N^{\ell-2}|F|}{t}\right) O ( ( t N ℓ − 2 ∣ F ∣ ) ) choices for t t t tuples ( b i , c i ) (b_i,c_i) ( b i , c i ) with ∣ O ( b i ) ∪ c i ∣ = ℓ |\mathcal{O}(b_i)\cup c_i|=\ell ∣ O ( b i ) ∪ c i ∣ = ℓ and O ( b i ) ∩ c i ≠ ∅ \mathcal{O}(b_i)\cap c_i\ne\varnothing O ( b i ) ∩ c i = ∅ . If we require that the ( b i , c i ) (b_i,c_i) ( b i , c i ) are pairwise orbit-disjoint, then the probability that all their elements are in C C C is p t ℓ p^{t\ell} p t ℓ unless zero is in one of the b i b_i b i . Without loss of generality b 1 b_1 b 1 has the zero, which gives a factor Ω ( N ) \Omega(N) Ω ( N ) less in the number of possible b 1 b_1 b 1 , a factor t t t extra in the binomial and a factor p p p less in the probability that b 1 ⊂ C b_1\subset C b 1 ⊂ C . This gives a factor O ( t / ( N p ) ) O(t/(Np)) O ( t / ( N p )) extra. This factor goes to zero, so this case has even smaller probability. Therefore there is a constant C k C_k C k only dependent on k k k such that the probability that A ℓ A_\ell A ℓ holds is at most
( O ( N ℓ − 2 ∣ F ∣ t ) ) p t ℓ ≤ ( C k N ℓ − 2 ∣ F ∣ p ℓ t ) t = ( C k N − 2 + ℓ / k ( ln N ) ℓ / k ∣ F ∣ t ) t . (2) \left(O\left(\frac{N^{\ell-2}|F|}{t}\right)\right)p^{t\ell}
\le\left(C_k\frac{N^{\ell-2}|F|p^\ell}{t}\right)^t
=\left(C_k\frac{N^{-2+\ell/k}(\ln N)^{\ell/k}|F|}{t}\right)^t . \tag*{(2)} ( O ( t N ℓ − 2 ∣ F ∣ ) ) p t ℓ ≤ ( C k t N ℓ − 2 ∣ F ∣ p ℓ ) t = ( C k t N − 2 + ℓ / k ( ln N ) ℓ / k ∣ F ∣ ) t . (2)
For ℓ ≤ 2 k − 2 \ell\le2k-2 ℓ ≤ 2 k − 2 , we have t = k + 1 t=k+1 t = k + 1 and ∣ F ∣ = O ~ ( N 1 / k ) |F|=\widetilde{O}(N^{1/k}) ∣ F ∣ = O ( N 1/ k ) , so this is O ~ ( N − 1 / k ) k + 1 = o ( 1 / N ) \widetilde{O}(N^{-1/k})^{k+1}=o(1/N) O ( N − 1/ k ) k + 1 = o ( 1/ N ) . For ℓ = 2 k − 1 \ell=2k-1 ℓ = 2 k − 1 , t = s = 1 k 2 ( k + 2 ) ln N t=s=\frac{1}{k^2(k+2)}\ln N t = s = k 2 ( k + 2 ) 1 ln N , and ∣ F ∣ ≤ D N 1 / k ( ln N ) − ( k − 1 ) / k |F|\le DN^{1/k}(\ln N)^{-(k-1)/k} ∣ F ∣ ≤ D N 1/ k ( ln N ) − ( k − 1 ) / k we get that
P ( A 2 k − 1 ) ≤ ( C k ⋅ D ⋅ k 2 ( k + 2 ) ) s = o ( 1 N ) , \mathbb{P}(A_{2k-1}) \le\left(C_k \cdot D \cdot k^2(k+2)\right)^s = o\left(\frac{1}{N}\right), P ( A 2 k − 1 ) ≤ ( C k ⋅ D ⋅ k 2 ( k + 2 ) ) s = o ( N 1 ) ,
for sufficiently small D D D .
Remark. The condition k ( k − 1 ) + s ≤ 2 s k(k-1)+s \le2s k ( k − 1 ) + s ≤ 2 s implies that the result requires that N = 2 Ω ( k 5 ) N = 2^{\Omega(k^5)} N = 2 Ω ( k 5 ) . This can be slightly improved to N = k Ω ( k 4 ) N = k^{\Omega(k^4)} N = k Ω ( k 4 ) by noting that for each A ℓ A_\ell A ℓ we can take t = k + 1 2 k − ℓ − 1 t = \frac{k+1}{2k-\ell-1} t = 2 k − ℓ − 1 k + 1 .
The weighted inertia bound is far from tight for graph powers
With this theorem in hand we can now present, for each fixed k ≥ 3 k \ge3 k ≥ 3 , our construction of graphs G n G_n G n that have α k ( G n ) = 2 \alpha_k(G_n) = 2 α k ( G n ) = 2 and n ≥ 0 ( G n k ) = Ω ~ ( n 1 / ( 6 k ) ) n_{\ge0}(G_n^k) = \widetilde{\Omega}(n^{1/(6k)}) n ≥ 0 ( G n k ) = Ω ( n 1/ ( 6 k ) ) . The graphs G k G^k G k will be random Cayley graphs, which gives us control over their second largest eigenvalue.
Theorem 13 [11 ] . For every abelian group Γ \Gamma Γ of odd order n n n and for every ℓ = o ( n ) \ell= o(n) ℓ = o ( n ) , if S S S is a set of ℓ \ell ℓ random members of Γ \Gamma Γ , then with high probability λ ( A ( Cay ( Γ , S ∪ − S ) ) ) = O ( ℓ log n ) \lambda(A(\operatorname{Cay}(\Gamma,S\cup-S))) = O(\sqrt{\ell\log n}) λ ( A ( Cay ( Γ , S ∪ − S ))) = O ( ℓ log n ) .
Remark. Compared to the original statement the additional requirements that Γ \Gamma Γ has odd order and ℓ = o ( n ) \ell= o(\sqrt{n}) ℓ = o ( n ) imply that the multigraph X ( Γ , S ) X(\Gamma,S) X ( Γ , S ) in [11 ] is the simple graph Cay ( Γ , S ∪ − S ) \operatorname{Cay}(\Gamma,S\cup-S) Cay ( Γ , S ∪ − S ) with high probability, because x ≠ − x x \ne-x x = − x and P ( ∃ x : x , − x ∈ S ) ≤ n ( ℓ n ) 2 = o ( 1 ) \mathbb{P}(\exists x : x,-x \in S) \le n\left(\frac{\ell}{n}\right)^2 = o(1) P ( ∃ x : x , − x ∈ S ) ≤ n ( n ℓ ) 2 = o ( 1 ) .
Theorem 14. For fixed k ≥ 3 k \ge3 k ≥ 3 there is a sequence of graphs G n G_n G n of order N N N such that α k ( G n ) = 2 \alpha_k(G_n) = 2 α k ( G n ) = 2 and n ≥ 0 ( G n k ) ≥ Ω ~ ( N 1 / ( 6 k ) ) n_{\ge0}(G_n^k) \ge\widetilde{\Omega}(N^{1/(6k)}) n ≥ 0 ( G n k ) ≥ Ω ( N 1/ ( 6 k ) ) .
Proof. For a fixed k ≥ 3 k \ge3 k ≥ 3 we pick some prime q > k q > k q > k and then for each n n n we consider random sets S ⊆ ( Z / q Z ) n ∖ { 0 } S \subseteq(\mathbb{Z}/q\mathbb{Z})^n \setminus\{0\} S ⊆ ( Z / q Z ) n ∖ { 0 } where each non-zero element is included with probability p ( n ) = D p N ( 1 − k ) / k ( log N ) − ( k − 1 ) / k p(n) = D_p N^{(1-k)/k}(\log N)^{-(k-1)/k} p ( n ) = D p N ( 1 − k ) / k ( log N ) − ( k − 1 ) / k (where N = q n N = q^n N = q n ) for small enough constant D p D_p D p . With high probability the set S ∪ − S S\cup-S S ∪ − S will have
size Θ ( N 1 / k ( log N ) ( 1 − k ) / k ) \Theta(N^{1/k}(\log N)^{(1-k)/k}) Θ ( N 1/ k ( log N ) ( 1 − k ) / k ) ,
no triples x , y , z x,y,z x , y , z with x + y + z = 0 x+y+z=0 x + y + z = 0 ,
λ ( A ( Cay ( Γ , S ∪ − S ) ) ) = O ( N 1 / 2 k log 1 / 2 k N ) \lambda(A(\operatorname{Cay}(\Gamma,S\cup-S))) = O(N^{1/2k}\log^{1/2k}N) λ ( A ( Cay ( Γ , S ∪ − S ))) = O ( N 1/2 k log 1/2 k N ) .
These conditions follow from the following standard inequalities. Let Y Y Y be the random variable that counts the number of triples x , y , z ∈ S ∪ − S x,y,z \in S\cup-S x , y , z ∈ S ∪ − S such that x + y + z = 0 x+y+z=0 x + y + z = 0 . Note that 0 ∉ S ∪ − S 0 \notin S\cup-S 0 ∈ / S ∪ − S , so in counting tuples for Y Y Y none of x , y , z x,y,z x , y , z can be inverses of another. As q > 3 q>3 q > 3 not all three can be equal. Hence x , y , z x,y,z x , y , z are independently included unless two are equal. There are N − 1 N-1 N − 1 tuples with x = y x=y x = y as z = − 2 x z=-2x z = − 2 x in that case. The equalities x = z x=z x = z and y = z y=z y = z hold similarly often. The number of triples where x , y , z x,y,z x , y , z are all distinct is at most N 2 N^2 N 2 , because two values determine the third. The probability that one element is in S ∪ − S S\cup-S S ∪ − S is 2 p − p 2 2p-p^2 2 p − p 2 , hence E ( Y ) ≤ 3 N ( 2 p − p 2 ) 2 + N 2 ( 2 p − p 2 ) 3 = o ( 1 ) \mathbb{E}(Y) \le3N(2p-p^2)^2+N^2(2p-p^2)^3=o(1) E ( Y ) ≤ 3 N ( 2 p − p 2 ) 2 + N 2 ( 2 p − p 2 ) 3 = o ( 1 ) , so by Markov’s inequality P ( Y ≥ 1 ) → 0 \mathbb{P}(Y\ge1)\to0 P ( Y ≥ 1 ) → 0 .
By Chernoff’s bound we have P ( ∣ S ∣ − ( N − 1 ) p ( N ) ∣ ≥ 1 2 ( N − 1 ) p ( N ) ) ≤ 2 e − 1 12 N p ( N ) → 0 \mathbb{P}(|S|-(N-1)p(N)| \ge\frac{1}{2}(N-1)p(N)) \le2e^{-\frac{1}{12}Np(N)} \to0 P ( ∣ S ∣ − ( N − 1 ) p ( N ) ∣ ≥ 2 1 ( N − 1 ) p ( N )) ≤ 2 e − 12 1 N p ( N ) → 0 , so ∣ S ∪ − S ∣ |S \cup-S| ∣ S ∪ − S ∣ , which is sandwiched between ∣ S ∣ |S| ∣ S ∣ and 2 ∣ S ∣ 2|S| 2∣ S ∣ has the right size. The last condition follows from Theorem 13 with ∣ S ∣ = Θ ( N 1 / k ( log N ) ( 1 − k ) / k ) |S| = \Theta(N^{1/k}(\log N)^{(1-k)/k}) ∣ S ∣ = Θ ( N 1/ k ( log N ) ( 1 − k ) / k ) .
Pick a random S S S that satisfies all three conditions. Then ∣ S ∣ = Θ ( N 1 / k ( log N ) ( 1 − k ) / k ) |S| = \Theta(N^{1/k}(\log N)^{(1-k)/k}) ∣ S ∣ = Θ ( N 1/ k ( log N ) ( 1 − k ) / k ) and we can choose D p D_p D p small enough that Theorem 7 applies with F : = S ∪ − S F := S \cup-S F := S ∪ − S . Let A A A be the symmetric set from the theorem. Choose G n = Cay ( ( Z / q Z ) n , A ∖ 0 ) G_n = \operatorname{Cay}((\mathbb{Z}/q\mathbb{Z})^n,A \setminus0) G n = Cay (( Z / q Z ) n , A ∖ 0 ) . As 0 ∈ A 0 \in A 0 ∈ A we find that A ⊆ A + A A \subseteq A+A A ⊆ A + A and hence G n k = Cay ( ( Z / q Z ) n , k A ∖ 0 ) G_n^k = \operatorname{Cay}((\mathbb{Z}/q\mathbb{Z})^n,kA \setminus0) G n k = Cay (( Z / q Z ) n , k A ∖ 0 ) , which implies that G n k ‾ = Cay ( ( Z / q Z ) n , F ) \overline{G_n^k} = \operatorname{Cay}((\mathbb{Z}/q\mathbb{Z})^n,F) G n k = Cay (( Z / q Z ) n , F ) . This is a triangle-free graph, because F F F has no triples summing to zero. It is also a ( N , ∣ F ∣ , O ( ∣ F ∣ log N ) ) (N,|F|,O(\sqrt{|F|}\log N)) ( N , ∣ F ∣ , O ( ∣ F ∣ log N )) -graph. Theorem 3 applies, so G n G_n G n is a graph with α k ( G n ) = 2 \alpha_k(G_n)=2 α k ( G n ) = 2 and n ≥ 0 ( G n k ) ≥ ( d + λ d + λ ) 1 / 3 = Ω ~ ( ∣ F ∣ 1 / 6 ) = Ω ~ ( N 1 / ( 6 k ) ) n_{\geq0}(G_n^k) \geq\left(\frac{d+\lambda}{d+\lambda}\right)^{1/3} = \widetilde{\Omega}(|F|^{1/6}) = \widetilde{\Omega}(N^{1/(6k)}) n ≥ 0 ( G n k ) ≥ ( d + λ d + λ ) 1/3 = Ω ( ∣ F ∣ 1/6 ) = Ω ( N 1/ ( 6 k ) ) .
Remark. For k = 2 k=2 k = 2 we cannot use the same p ( N ) p(N) p ( N ) , because the triangle-free condition requires p ( N ) = o ( N − 2 / 3 ) p(N)=o(N^{-2/3}) p ( N ) = o ( N − 2/3 ) . The same argument with q > 3 q>3 q > 3 and p ( N ) = N − 2 / 3 / h ( N ) p(N)=N^{-2/3}/h(N) p ( N ) = N − 2/3 / h ( N ) , where h h h is a function that goes to infinity very slowly, gives n ≥ 0 ( G n 2 ) ≥ Ω ( ( N 1 / 3 h ( n ) log N ) 1 / 6 ) n_{\geq0}(G_n^2) \geq\Omega\left(\left(\frac{N^{1/3}}{h(n)\log N}\right)^{1/6}\right) n ≥ 0 ( G n 2 ) ≥ Ω ( ( h ( n ) l o g N N 1/3 ) 1/6 ) which is only slightly better than our bound for k = 3 k=3 k = 3 .
Tightness of the inertia-type bound
The inertia-type bound is a bound that is computationally simpler to optimize than the weighted inertia bound. However, in return the bound is less strong [31 ] . In this section we prove extreme separation, where the inertia-type bound grows linearly in the order and the k k k -independence number is 1 1 1 , i.e. the graph power is complete. We show this separation for large random graphs. One may suspect that the bad performance comes from the non-constant diagonal of p ( A ) p(A) p ( A ) , or more generally, the lack of symmetries, in these random graphs. However, we also give an example of vertex-transitive graphs with the same extreme separation. Furthermore, this construction is explicit. Both the random graphs and our explicit graphs have α k ( G ) = 1 \alpha_k(G)=1 α k ( G ) = 1 for k ≥ 2 k \geq2 k ≥ 2 , which even the unweighted inertia bound on G k G^k G k can recognise, but the inertia-type bound on G G G cannot.
Roughly speaking, our graphs must satisfy two conditions: every vertex is reachable in at most k k k steps, while the normalized spectral distribution has large enough support to force a linear amount of eigenvalues of both signs for all polynomials. We establish the latter through convergence of the spectral distribution to distributions with infinite support.
In particular for random graphs we mention Wigner’s semicircle law: the probability distribution on [ − 2 , 2 ] [-2,2] [ − 2 , 2 ] with density function 1 2 π 4 − x 2 \frac{1}{2\pi}\sqrt{4-x^2} 2 π 1 4 − x 2 and associated distribution function F s c F_{\mathrm{sc}} F sc and measure μ s c \mu_{\mathrm{sc}} μ sc . For a multiset B B B the empirical distribution is the distribution of a random element. For a Hermitian n × n n \times n n × n -matrix M M M the Empirical Spectral Distribution (ESD) is the probability distribution with distribution function F M ( x ) : = 1 n ∣ { i : λ i ≤ x } ∣ F_M(x):=\frac{1}{n}|\{i:\lambda_i\leq x\}| F M ( x ) := n 1 ∣ { i : λ i ≤ x } ∣ .
Recall that P k P_k P k denotes the vector space of real polynomials of degree at most k k k and that In k ( p , G ) \operatorname{In}_k(p,G) In k ( p , G ) represents the inertia-type bound using a polynomial p ∈ P k p \in P_k p ∈ P k . If X X X is a random variable which uniformly picks an eigenvalue of G G G , then for all p ∈ P k p \in P_k p ∈ P k ,
In k ( p , G ) = min { ∣ { i : p ( λ i ) ≤ W ( p ) } ∣ , ∣ { i : p ( λ i ) ≥ w ( p ) } ∣ } = n ⋅ min { P ( p ( X ) ≤ W ( p ) ) , P ( p ( X ) ≥ w ( p ) ) } . \operatorname{In}_k(p,G)=\min\{|\{i:p(\lambda_i)\leq W(p)\}|,|\{i:p(\lambda_i)\geq w(p)\}|\}
= n\cdot\min\{\mathbb{P}(p(X)\leq W(p)),\mathbb{P}(p(X)\geq w(p))\}. In k ( p , G ) = min { ∣ { i : p ( λ i ) ≤ W ( p )} ∣ , ∣ { i : p ( λ i ) ≥ w ( p )} ∣ } = n ⋅ min { P ( p ( X ) ≤ W ( p )) , P ( p ( X ) ≥ w ( p ))} .
The average diagonal value of p ( A ) p(A) p ( A ) is 1 n tr p ( A ) \frac{1}{n}\operatorname{tr} p(A) n 1 tr p ( A ) . It is well-known that the trace is equal to the sum of the eigenvalues, so w ‾ ( p ) ≤ 1 n ∑ p ( λ i ) = E [ p ( X ) ] ≤ W ( p ) \overline{w}(p) \le\frac{1}{n}\sum p(\lambda_i)=\mathbb{E}[p(X)] \le W(p) w ( p ) ≤ n 1 ∑ p ( λ i ) = E [ p ( X )] ≤ W ( p ) and therefore
Ink k ( p , G ) ≥ n ⋅ min { P ( p ( X ) ≤ E [ p ( X ) ] ) , P ( p ( X ) ≥ E [ p ( X ) ] ) } . (3) \operatorname{Ink}_k(p,G) \ge n\cdot\min\{\mathbb{P}(p(X)\le\mathbb{E}[p(X)]),\mathbb{P}(p(X)\ge\mathbb{E}[p(X)])\}. \tag*{(3)} Ink k ( p , G ) ≥ n ⋅ min { P ( p ( X ) ≤ E [ p ( X )]) , P ( p ( X ) ≥ E [ p ( X )])} . (3)
We bound these probabilities for certain sequences of converging measures and show that the ESDs form such a sequence.
Lemma 15. Fix an integer k ≥ 1 k\ge1 k ≥ 1 . Let μ \mu μ be a probability measure supported on a compact interval I ⊆ R I\subseteq\mathbb{R} I ⊆ R , with μ ( S ) < 1 \mu(S)<1 μ ( S ) < 1 for any set S ⊆ I S\subseteq I S ⊆ I of size at most k k k . Let ( μ n ) n = 1 ∞ (\mu_n)_{n=1}^{\infty} ( μ n ) n = 1 ∞ be probability measures on R \mathbb{R} R . Define
S k : = { r ∈ P k : ∥ r ∥ ∞ , I = 1 } , where ∥ r ∥ ∞ , I : = max x ∈ I ∣ r ( x ) ∣ . S_k:=\{r\in P_k:\|r\|_{\infty,I}=1\},\qquad\text{where }\|r\|_{\infty,I}:=\max_{x\in I}|r(x)|. S k := { r ∈ P k : ∥ r ∥ ∞ , I = 1 } , where ∥ r ∥ ∞ , I := x ∈ I max ∣ r ( x ) ∣. Assume that
sup r ∈ S k ∣ ∫ R ∣ r ∣ d μ n − ∫ I ∣ r ∣ d μ ∣ → 0 \sup_{r\in S_k}\left|\int_{\mathbb{R}}|r|\,d\mu_n-\int_I|r|\,d\mu\right|\to0 r ∈ S k sup ∫ R ∣ r ∣ d μ n − ∫ I ∣ r ∣ d μ → 0 and
sup r ∈ S k ∫ R ∖ I ∣ r ∣ d μ n → 0. \sup_{r\in S_k}\int_{\mathbb{R}\setminus I}|r|\,d\mu_n\to0. r ∈ S k sup ∫ R ∖ I ∣ r ∣ d μ n → 0. Then there exists a constant ε = ε ( k , μ , I ) > 0 \varepsilon=\varepsilon(k,\mu,I)>0 ε = ε ( k , μ , I ) > 0 and an integer N N N such that, for all n > N n>N n > N and all p ∈ P k p\in P_k p ∈ P k , if X n ∼ μ n X_n\sim\mu_n X n ∼ μ n , then
P ( p ( X n ) ≥ E [ p ( X n ) ] ) ≥ ε and P ( p ( X n ) ≤ E [ p ( X n ) ] ) ≥ ε . \mathbb{P}(p(X_n)\ge\mathbb{E}[p(X_n)])\ge\varepsilon
\qquad\text{and}\qquad
\mathbb{P}(p(X_n)\le\mathbb{E}[p(X_n)])\ge\varepsilon. P ( p ( X n ) ≥ E [ p ( X n )]) ≥ ε and P ( p ( X n ) ≤ E [ p ( X n )]) ≥ ε .
Proof. The functions ∥ r ∥ ∞ , I \|r\|_{\infty,I} ∥ r ∥ ∞ , I and
∥ r ∥ 1 , μ : = ∫ I ∣ r ∣ d μ \|r\|_{1,\mu}:=\int_I|r|\,d\mu ∥ r ∥ 1 , μ := ∫ I ∣ r ∣ d μ
are norms on P k P_k P k , because μ ( S ) < 1 \mu(S)<1 μ ( S ) < 1 on the roots of any nonzero polynomial of degree at most k k k . Since P k P_k P k is finite-dimensional and I I I is compact these norms are equivalent on P k P_k P k . The equivalence of norms means that there exists c > 0 c>0 c > 0 such that ∥ r ∥ 1 , μ ≥ c ∥ r ∥ ∞ , I \|r\|_{1,\mu}\ge c\|r\|_{\infty,I} ∥ r ∥ 1 , μ ≥ c ∥ r ∥ ∞ , I for every r ∈ P k r\in P_k r ∈ P k . The value of this c c c is exactly
c : = inf r ∈ S k ∫ I ∣ r ∣ d μ > 0. c:=\inf_{r\in S_k}\int_I|r|\,d\mu>0. c := r ∈ S k inf ∫ I ∣ r ∣ d μ > 0.
By the two assumptions, for all sufficiently large n n n ,
sup r ∈ S k ∣ ∫ R ∣ r ∣ d μ n − ∫ I ∣ r ∣ d μ ∣ ≤ c 4 (4) \sup_{r\in S_k}\left|\int_{\mathbb{R}}|r|\,d\mu_n-\int_I|r|\,d\mu\right|\le\frac{c}{4} \tag*{(4)} r ∈ S k sup ∫ R ∣ r ∣ d μ n − ∫ I ∣ r ∣ d μ ≤ 4 c (4)
and
sup r ∈ S k ∫ R ∖ I ∣ r ∣ d μ n ≤ c 8 . (5) \sup_{r\in S_k}\int_{\mathbb{R}\setminus I}|r|\,d\mu_n\le\frac{c}{8}. \tag*{(5)} r ∈ S k sup ∫ R ∖ I ∣ r ∣ d μ n ≤ 8 c . (5)
We claim that ε = c / 4 \varepsilon=c/4 ε = c /4 works. Fix p ∈ P k p \in\mathcal{P}_k p ∈ P k . If p p p is constant, the claim is immediate. Otherwise, set m n : = ∫ R p d μ n m_n := \int_{\mathbb{R}} p\,d\mu_n m n := ∫ R p d μ n , which is finite because p p p is bounded on I I I and because (5) holds, and define the polynomial
r n : = p − m n ∥ p − m n ∥ ∞ , I , r_n := \frac{p-m_n}{\lVert p-m_n\rVert_{\infty,I}}, r n := ∥ p − m n ∥ ∞ , I p − m n ,
which can be viewed as a normalization of p p p . Then r n ∈ S k r_n \in\mathcal{S}_k r n ∈ S k , so writing r n + = max ( r n , 0 ) r_n^+ = \max(r_n,0) r n + = max ( r n , 0 ) we have 0 ≤ r n + ≤ 1 0 \le r_n^+ \le1 0 ≤ r n + ≤ 1 on I I I and thus
P ( p ( X n ) ≥ m n ) = P ( r n ( X n ) ≥ 0 ) ≥ ∫ I 1 { r n ≥ 0 } d μ n ≥ ∫ I r n + d μ n . \mathbb{P}(p(X_n) \ge m_n) = \mathbb{P}(r_n(X_n) \ge0) \ge\int_I \mathbf{1}_{\{r_n\ge0\}}d\mu_n \ge\int_I r_n^+d\mu_n. P ( p ( X n ) ≥ m n ) = P ( r n ( X n ) ≥ 0 ) ≥ ∫ I 1 { r n ≥ 0 } d μ n ≥ ∫ I r n + d μ n .
By definition of m n m_n m n we get that ∫ R r n d μ n = 0 \int_{\mathbb{R}}r_n\,d\mu_n=0 ∫ R r n d μ n = 0 , so
∫ R r n + d μ n = 1 2 ∫ R ∣ r n ∣ d μ n . \int_{\mathbb{R}}r_n^+\,d\mu_n = \frac{1}{2}\int_{\mathbb{R}}|r_n|\,d\mu_n. ∫ R r n + d μ n = 2 1 ∫ R ∣ r n ∣ d μ n .
Moreover by (4) ,
∫ R ∣ r n ∣ d μ n ≥ ∫ I ∣ r n ∣ d μ − c 4 ≥ 3 c 4 . \int_{\mathbb{R}}|r_n|\,d\mu_n \ge\int_I|r_n|\,d\mu-\frac{c}{4}\ge\frac{3c}{4}. ∫ R ∣ r n ∣ d μ n ≥ ∫ I ∣ r n ∣ d μ − 4 c ≥ 4 3 c .
Hence
∫ R r n + d μ n ≥ 3 c 8 . \int_{\mathbb{R}}r_n^+\,d\mu_n \ge\frac{3c}{8}. ∫ R r n + d μ n ≥ 8 3 c .
The contribution from outside I I I is at most the contribution of ∣ r n ∣ |r_n| ∣ r n ∣ which is at most c / 8 c/8 c /8 by (5) , so
∫ I r n + d μ n ≥ 3 c 8 − c 8 = c 4 . \int_I r_n^+\,d\mu_n \ge\frac{3c}{8}-\frac{c}{8}=\frac{c}{4}. ∫ I r n + d μ n ≥ 8 3 c − 8 c = 4 c .
Since 0 ≤ r n + ≤ 1 0 \le r_n^+ \le1 0 ≤ r n + ≤ 1 on I I I , it follows that P ( r n ( X n ) ≥ 0 ) ≥ c 4 \mathbb{P}(r_n(X_n)\ge0)\ge\frac{c}{4} P ( r n ( X n ) ≥ 0 ) ≥ 4 c . Equivalently,
P ( p ( X n ) ≥ m n ) ≥ c 4 . \mathbb{P}(p(X_n)\ge m_n)\ge\frac{c}{4}. P ( p ( X n ) ≥ m n ) ≥ 4 c .
Applying the same argument to − p -p − p gives P ( p ( X n ) ≤ m n ) ≥ c 4 \mathbb{P}(p(X_n)\le m_n)\ge\frac{c}{4} P ( p ( X n ) ≤ m n ) ≥ 4 c . This proves the lemma.
Remark. When μ = μ s c \mu=\mu_{sc} μ = μ sc is the semicircle law, then we can show that ε ≥ 3 30 π k 3 \varepsilon\ge\frac{\sqrt{3}}{30\pi k^3} ε ≥ 30 π k 3 3 . In [50 ] the author studied for r ∈ P k r\in\mathcal{P}_k r ∈ P k with ∫ [ − 1 , 1 ] r d ν = 0 \int_{[-1,1]}r\,d\nu=0 ∫ [ − 1 , 1 ] r d ν = 0 and ν = ( 1 − x 2 ) α \nu=(1-x^2)^\alpha ν = ( 1 − x 2 ) α the value of
min r ∫ χ ( r ) d ν \min_r \int_{\chi(r)}d\nu r min ∫ χ ( r ) d ν
where χ ( r ) = { x ∈ [ − 1 , 1 ] : r ( x ) ≥ 0 } \chi(r)=\{x\in[-1,1]:r(x)\ge0\} χ ( r ) = { x ∈ [ − 1 , 1 ] : r ( x ) ≥ 0 } . Tikhanovtseva showed that this minimum grows as Θ ( k − 2 ( α + 1 ) ) \Theta(k^{-2(\alpha+1)}) Θ ( k − 2 ( α + 1 ) ) as a function of k k k . For α = 1 2 \alpha=\frac{1}{2} α = 2 1 this gives the minimum for (a scaled) semicircular law. This does not immediately apply to Lemma 15 , because we have a sequence of measures converging to μ \mu μ . However, a proof in that paper does suggest a lower bound on c c c . See the proof of Lemma 2 in [50 ] for the details. Fix a polynomial r ∈ S k r\in\mathcal{S}_k r ∈ S k and let t 2 t_2 t 2 be a point such that ∣ r ( t 2 ) ∣ = 1 |r(t_2)|=1 ∣ r ( t 2 ) ∣ = 1 . Use Markov’s inequality on polynomials to lower bound ∣ r ( t ) ∣ ≥ 1 − k 2 ∣ t − t 2 ∣ |r(t)| \ge1-k^2|t-t_2| ∣ r ( t ) ∣ ≥ 1 − k 2 ∣ t − t 2 ∣ . Following the same chain of inequalities we get
∫ [ − 2 , 2 ] ∣ r ∣ d μ s c ≥ ∫ [ − 2 , 2 ] ∩ [ t 2 − 1 k 2 , t 2 + 1 k 2 ] ( 1 − k 2 ∣ t − t 2 ∣ ) d μ s c ≥ 1 2 π ∫ [ 0 , 1 k 2 ] ( 4 x − x 2 ) 1 / 2 ( 1 − k 2 x ) d x ≥ 3 2 π ( 1 / 2 + 1 ) ( 1 / 2 + 2 ) 1 k 2 ( 1 / 2 + 1 ) . \begin{aligned}
\int_{[-2,2]} |r|\,d\mu_{\mathrm{sc}} \ge\int_{[-2,2]\cap[t_2-\frac{1}{k^2},t_2+\frac{1}{k^2}]} (1-k^2|t-t_2|)\,d\mu_{\mathrm{sc}} \ge\frac{1}{2\pi}\int_{[0,\frac{1}{k^2}]}(4x-x^2)^{1/2}(1-k^2x)\,dx \\
&\ge\frac{\sqrt{3}}{2\pi(1/2+1)(1/2+2)}\frac{1}{k^{2(1/2+1)}}.
\end{aligned} ∫ [ − 2 , 2 ] ∣ r ∣ d μ sc ≥ ∫ [ − 2 , 2 ] ∩ [ t 2 − k 2 1 , t 2 + k 2 1 ] ( 1 − k 2 ∣ t − t 2 ∣ ) d μ sc ≥ 2 π 1 ∫ [ 0 , k 2 1 ] ( 4 x − x 2 ) 1/2 ( 1 − k 2 x ) d x ≥ 2 π ( 1/2 + 1 ) ( 1/2 + 2 ) 3 k 2 ( 1/2 + 1 ) 1 .
Hence c ≥ 4 3 30 π k − 3 c\ge\frac{4\sqrt{3}}{30\pi}k^{-3} c ≥ 30 π 4 3 k − 3 .
The optimal inertia-type bound is far from tight for random graphs
Many models of random Hermitian matrices have spectral distribution converging to the semicircle law in probability, see e.g. [12 ] . This also holds for the normalized adjacency matrix of a G ( n , p ) G(n,p) G ( n , p ) graph. This was stated and shown explicitly in [51 ] . Note that the authors do not explicitly mention that the convergence happens ‘in probability’, but that this is the type of convergence present in Wigner’s original result.
Theorem 16 ([51 Theorem 1.3] ). Consider the random graphs G ( n , p ) G(n,p) G ( n , p ) where n p ( 1 − p ) → ∞ np(1-p)\to\infty n p ( 1 − p ) → ∞ as n → ∞ n\to\infty n → ∞ . Let A ( G ) A(G) A ( G ) denote the adjacency matrix of the graph G G G . The empirical spectral distribution of the matrix
1 n p ( 1 − p ) A ( G ( n , p ) ) \frac{1}{\sqrt{np(1-p)}}A(G(n,p)) n p ( 1 − p ) 1 A ( G ( n , p )) converges in probability to the semicircle distribution.
Much stronger local semicircle laws have been proven, see e.g. [16 ] , but the convergence on global scale suffices for our purposes.
Corollary 17. Fix k ≥ 2 k\ge2 k ≥ 2 . Let q n q_n q n be a sequence of edge probabilities such that as n → ∞ n\to\infty n → ∞ , with d n : = n q n d_n:=nq_n d n := n q n ,
q n → 0 , d n → ∞ , d n k n = ω ( log n ) , d n = o ( n 2 / k ) . q_n\to0,\qquad d_n\to\infty,\qquad\frac{d_n^k}{n}=\omega(\log n),\qquad d_n=o(n^{2/k}). q n → 0 , d n → ∞ , n d n k = ω ( log n ) , d n = o ( n 2/ k ) . Let G n = G ( n , q n ) G_n=G(n,q_n) G n = G ( n , q n ) . Then, with high probability,
α k ( G n ) = 1 and In k ( G n ) = Ω ( n ) . \alpha_k(G_n)=1 \qquad\text{and}\qquad\operatorname{In}_k(G_n)=\Omega(n). α k ( G n ) = 1 and In k ( G n ) = Ω ( n ) . In particular, this holds for q n = n − 1 + 3 2 k q_n=n^{-1+\frac{3}{2k}} q n = n − 1 + 2 k 3 .
Proof. Let σ n : = n q n ( 1 − q n ) \sigma_n:=\sqrt{nq_n(1-q_n)} σ n := n q n ( 1 − q n ) and M n : = σ n − 1 A ( G n ) M_n:=\sigma_n^{-1}A(G_n) M n := σ n − 1 A ( G n ) . Denote the eigenvalues of M n M_n M n by ξ 1 , … , ξ n \xi_1,\ldots,\xi_n ξ 1 , … , ξ n , and let μ n \mu_n μ n be their empirical spectral distribution.
We use two standard spectral facts for G ( n , q n ) G(n,q_n) G ( n , q n ) in this regime. First, μ n \mu_n μ n converges weakly in probability to the semicircle law μ s c \mu_{\mathrm{sc}} μ sc , because d n → ∞ d_n\to\infty d n → ∞ , see Theorem 16 . Second, applying Lemma 4.3 and Remark 2.4 of [27 ] to M n − q n σ n ( J − I ) M_n-\frac{q_n}{\sigma_n}(J-I) M n − σ n q n ( J − I ) , says that all non-Perron eigenvalues of M n M_n M n lie in a fixed compact interval, say [ − T , T ] [-T,T] [ − T , T ] with $T slightly larger than 2 for large n n n . It also follows that the Perron eigenvalue satisfies ∣ ξ 1 ∣ = O ( d n ) |\xi_1| = O(\sqrt{d_n}) ∣ ξ 1 ∣ = O ( d n ) .
Let I = [ − 2 , 2 ] I = [-2,2] I = [ − 2 , 2 ] . The semicircle measure μ s c \mu_{sc} μ sc is supported on I I I and has density strictly positive almost everywhere on I I I .
We verify the hypotheses of Lemma 15 . Let S k : = { r ∈ P k : ∥ r ∥ ∞ , I = 1 } S_k := \{r \in P_k : \|r\|_{\infty,I} = 1\} S k := { r ∈ P k : ∥ r ∥ ∞ , I = 1 } . Since S k S_k S k is compact in the finite-dimensional space P k P_k P k , there is a constant C k > 0 C_k > 0 C k > 0 such that, for all r ∈ S k r \in S_k r ∈ S k ,
∣ r ( x ) ∣ ≤ C k ( 1 + ∣ x ∣ k ) for all x ∈ R . |r(x)| \le C_k(1+|x|^k) \qquad\text{for all } x \in\mathbb{R}. ∣ r ( x ) ∣ ≤ C k ( 1 + ∣ x ∣ k ) for all x ∈ R .
Therefore the Perron eigenvalue contributes at most
1 n sup r ∈ S k ∣ r ( ξ 1 ) ∣ ≤ O ( 1 + d n k / 2 n ) = o ( 1 ) (6) \frac{1}{n}\sup_{r\in S_k}|r(\xi_1)| \le O\left(\frac{1+d_n^{k/2}}{n}\right)=o(1) \tag*{(6)} n 1 r ∈ S k sup ∣ r ( ξ 1 ) ∣ ≤ O ( n 1 + d n k /2 ) = o ( 1 ) (6)
to ∫ R ∣ r ∣ d μ n \int_{\mathbb{R}} |r|\,d\mu_n ∫ R ∣ r ∣ d μ n , because d n = o ( n 2 / k ) d_n=o(n^{2/k}) d n = o ( n 2/ k ) .
On the remaining n − 1 n-1 n − 1 eigenvalues, the functions ∣ r ∣ |r| ∣ r ∣ , r ∈ S k r \in S_k r ∈ S k , are uniformly bounded and form a compact family of continuous functions on [ − T , T ] [-T,T] [ − T , T ] . Hence weak convergence in probability to μ s c \mu_{sc} μ sc implies, uniformly in r ∈ S k r \in S_k r ∈ S k , for all fixed δ > 0 \delta> 0 δ > 0
P ( ∣ ∫ R ∣ r ∣ d μ n − ∫ I ∣ r ∣ d μ s c ∣ ≥ δ ) → 0. \mathbb{P}\left(\left|\int_{\mathbb{R}} |r|\,d\mu_n-\int_I |r|\,d\mu_{sc}\right|\ge\delta\right)\to0. P ( ∫ R ∣ r ∣ d μ n − ∫ I ∣ r ∣ d μ sc ≥ δ ) → 0.
This is the right convergence for our argument. Fixing δ = c / 4 \delta= c/4 δ = c /4 , where c c c comes from the proof of Lemma 15 we see that (4) holds with high probability. The measure μ s c \mu_{sc} μ sc is supported on I = [ − 2 , 2 ] I = [-2,2] I = [ − 2 , 2 ] , has no atoms and ∣ r ∣ |r| ∣ r ∣ is bounded outside I I I except at ξ 1 \xi_1 ξ 1 , so combining (6) and weak convergence, the total ∣ r ∣ |r| ∣ r ∣ -weighted mass outside I I I is also negligible (with high probability) uniformly in r ∈ S k r \in S_k r ∈ S k :
sup r ∈ S k ∫ R ∖ I ∣ r ∣ d μ n → 0. \sup_{r\in S_k}\int_{\mathbb{R}\setminus I}|r|\,d\mu_n\to0. r ∈ S k sup ∫ R ∖ I ∣ r ∣ d μ n → 0.
Thus Lemma 15 applies.
Consequently, there exists ε > 0 \varepsilon> 0 ε > 0 , depending only on k k k , such that with high probability, for every r ∈ P k r \in P_k r ∈ P k ,
P ( r ( X n ) ≥ E [ r ( X n ) ] ) ≥ ε \mathbb{P}\bigl(r(X_n)\ge\mathbb{E}[r(X_n)]\bigr)\ge\varepsilon P ( r ( X n ) ≥ E [ r ( X n )] ) ≥ ε
and
P ( r ( X n ) ≤ E [ r ( X n ) ] ) ≥ ε , \mathbb{P}\bigl(r(X_n)\le\mathbb{E}[r(X_n)]\bigr)\ge\varepsilon, P ( r ( X n ) ≤ E [ r ( X n )] ) ≥ ε ,
where X n X_n X n is a uniformly chosen eigenvalue of M n M_n M n .
Now return to the unnormalized adjacency eigenvalues. If λ i = σ n ξ i \lambda_i=\sigma_n\xi_i λ i = σ n ξ i , then for every p ∈ P k p\in P_k p ∈ P k the polynomial
r ( x ) : = p ( σ n x ) r(x):=p(\sigma_n x) r ( x ) := p ( σ n x )
also belongs to P k P_k P k . Hence the preceding probability bounds apply to p ( λ i ) p(\lambda_i) p ( λ i ) , uniformly over all p ∈ P k p\in P_k p ∈ P k . Therefore by (3)
In k ( p , G n ) ≥ n ⋅ min { P ( p ( X ) ≤ E [ p ( X ) ] ) , P ( p ( X ) ≥ E [ p ( X ) ] ) } ≥ ε n , \operatorname{In}_k(p,G_n)\ge n\cdot\min\left\{\mathbb{P}(p(X)\le\mathbb{E}[p(X)]),\mathbb{P}(p(X)\ge\mathbb{E}[p(X)])\right\}\ge\varepsilon n, In k ( p , G n ) ≥ n ⋅ min { P ( p ( X ) ≤ E [ p ( X )]) , P ( p ( X ) ≥ E [ p ( X )]) } ≥ ε n ,
where X X X is a uniformly chosen eigenvalue of A ( G n ) A(G_n) A ( G n ) . Since this holds for all p ∈ P k p\in P_k p ∈ P k , we get In k ( G n ) = Ω ( n ) \operatorname{In}_k(G_n)=\Omega(n) In k ( G n ) = Ω ( n ) with high probability.
It remains to show that α k ( G n ) = 1 \alpha_k(G_n)=1 α k ( G n ) = 1 . By the standard diameter threshold for binomial random graphs, if
d n k n = ω ( log n ) , \frac{d_n^k}{n}=\omega(\log n), n d n k = ω ( log n ) ,
then G ( n , q n ) G(n,q_n) G ( n , q n ) has diameter at most k k k with high probability, see [18 Chapter 10] . This is one of our assumptions. Hence, with high probability, every two vertices of G n G_n G n are at distance at most k k k , and therefore α k ( G n ) = 1 \alpha_k(G_n)=1 α k ( G n ) = 1 . The proof is complete.
Finally, for the explicit choice q n = n − 1 + 3 / ( 2 k ) q_n=n^{-1+3/(2k)} q n = n − 1 + 3/ ( 2 k ) , we have d n = n q n = n 3 / ( 2 k ) d_n=nq_n=n^{3/(2k)} d n = n q n = n 3/ ( 2 k ) , so
d n k n = n 1 / 2 = ω ( log n ) \frac{d_n^k}{n}=n^{1/2}=\omega(\log n) n d n k = n 1/2 = ω ( log n )
and
d n k / 2 n = n − 1 / 4 → 0. \frac{d_n^{k/2}}{n}=n^{-1/4}\to0. n d n k /2 = n − 1/4 → 0.
Thus all assumptions above are satisfied.
An explicit vertex-transitive graph class with far from tight inertia-type bound
A graph is vertex-transitive when for any pair of vertices u , v u,v u , v there is an automorphism sending u u u to v v v . In this section we construct an explicit vertex-transitive graph that obtains the same separation as the random graphs in § 3.1 . When G G G is a vertex-transitive graph, such as a Cayley graph, the diagonal elements ( p ( A ) ) i i (p(A))_{ii} ( p ( A ) ) ii in the inertia-type bound from Theorem 2 are all equal and hence rephrasing using the empirical spectral distribution X X X and Y = p ( X ) Y=p(X) Y = p ( X ) , the inertia-type bound states
α k ( G ) ≤ n ⋅ min { P ( Y ≥ E [ Y ] ) , P ( Y ≤ E [ Y ] ) } . \alpha_k(G)\le n\cdot\min\{\mathbb{P}(Y\ge\mathbb{E}[Y]),\mathbb{P}(Y\le\mathbb{E}[Y])\}. α k ( G ) ≤ n ⋅ min { P ( Y ≥ E [ Y ]) , P ( Y ≤ E [ Y ])} .
In this section we prove the following result.
Theorem 18. Fix an integer k ≥ 5 k\ge5 k ≥ 5 and prime p > k p>k p > k . Define s = ⌊ k 2 ⌋ + 1 s=\left\lfloor\frac{k}{2}\right\rfloor+1 s = ⌊ 2 k ⌋ + 1 . There exists an integer a ≥ 1 a\ge1 a ≥ 1 such that s ∣ p 2 a − 1 s\mid p^{2a}-1 s ∣ p 2 a − 1 . For any large enough prime power q = ( p 2 a ) h q=(p^{2a})^h q = ( p 2 a ) h the graph
G q s : = Cay ( F q s , S s ) , where S s = { ± ( t , t 2 , … , t s ) : t ∈ F q × } G_q^s:=\operatorname{Cay}(\mathbb{F}_q^s,S_s),\qquad\text{where }S_s=\{\pm(t,t^2,\ldots,t^s):t\in\mathbb{F}_q^\times\} G q s := Cay ( F q s , S s ) , where S s = { ± ( t , t 2 , … , t s ) : t ∈ F q × } has
α k ( G q s ) = 1 , and In k ( G q s ) = Ω ( ∣ V ( G q s ) ∣ ) as q → ∞ . \alpha_k(G_q^s)=1,\qquad\text{and}\qquad\operatorname{In}_k(G_q^s)=\Omega(|V(G_q^s)|)\text{ as }q\to\infty. α k ( G q s ) = 1 , and In k ( G q s ) = Ω ( ∣ V ( G q s ) ∣ ) as q → ∞.
Remark. We should note that a similar result holds for k = 2 , 3 , 4 k=2,3,4 k = 2 , 3 , 4 , but the proofs given in this section work assuming k ≥ 5 k\ge5 k ≥ 5 . We outline here shortly what needs to change for the small k k k . For k = 4 k=4 k = 4 we can use the same families of graphs, but we need a different proof that the diameter is still at most k k k . For k = 2 , 3 k=2,3 k = 2 , 3 we have to rely on different graphs related to Kloosterman and Birch sums which also satisfy equidistribution. For k = 3 k=3 k = 3 we can use S = { ( t , t 3 ) : t ∈ F q × } S=\{(t,t^3):t\in\mathbb{F}_q^\times\} S = {( t , t 3 ) : t ∈ F q × } and rely on equidistribution of Birch sums as stated in [29 ] . It can be shown that these graphs have diameter 3. For k = 2 k=2 k = 2 one can use the ‘Euclidean’ Cayley graph with connection set { ( x , y , z , w ) ∈ F q 4 : x 2 + y 2 + z 2 + w 2 = 1 } \{(x,y,z,w)\in\mathbb{F}_q^4:x^2+y^2+z^2+w^2=1\} {( x , y , z , w ) ∈ F q 4 : x 2 + y 2 + z 2 + w 2 = 1 } , see [19 ] for the spectral properties and [45 ] for the diameter.
For a d d d -regular graph the normalized spectrum NSpec ( G ) \operatorname{NSpec}(G) NSpec ( G ) is obtained from Spec ( G ) \operatorname{Spec}(G) Spec ( G ) by dividing each element by d \sqrt{d} d .
Inspired by the work in [29 ] we seek a family of graphs defined by algebraic relations that have a spectrum converging to a distribution with infinite support.
In particular, we let p p p be an odd prime and q = p h q=p^h q = p h a power of p p p . We consider the Cayley graph G q s = Cay ( F q s , S ) G_q^s=\operatorname{Cay}(\mathbb{F}_q^s,S) G q s = Cay ( F q s , S ) for s ≥ 3 s\ge3 s ≥ 3 where S = { ± ( t , t 2 , … , t s ) : t ∈ F q × } S=\{\pm(t,t^2,\ldots,t^s):t\in\mathbb{F}_q^{\times}\} S = { ± ( t , t 2 , … , t s ) : t ∈ F q × } . This graph has order n = q s n=q^s n = q s and degree 2 ( q − 1 ) 2(q-1) 2 ( q − 1 ) . We show that the non-principal eigenvalues are of order at most q \sqrt{q} q and that the normalized spectrum converges to a distribution with infinite support. The same argument as found in Corollary 17 then implies that In k ( G q s ) ≥ Ω ( n ) \operatorname{In}_k(G_q^s)\ge\Omega(n) In k ( G q s ) ≥ Ω ( n ) . Additionally, we show that for s = ⌊ k 2 ⌋ + 1 s=\left\lfloor\frac{k}{2}\right\rfloor+1 s = ⌊ 2 k ⌋ + 1 this graph has diameter at most k k k which implies that α k ( G q s ) = 1 \alpha_k(G_q^s)=1 α k ( G q s ) = 1 .
For the diameter we use Cohen’s result that all factorization patterns of polynomials are almost equally common [22 ] . For a partition λ \lambda λ of n n n let T ( λ ) T(\lambda) T ( λ ) be the proportion of elements in the symmetric group with cycle pattern λ \lambda λ . For a field F \mathbb{F} F and a polynomial P ∈ F [ x ] P\in\mathbb{F}[x] P ∈ F [ x ] the factorization pattern is the multiset of degrees of the irreducible factors of P P P .
Theorem 19 [22 ] . Let A A A be a set consisting of all polynomials in F q [ x ] \mathbb{F}_q[x] F q [ x ] of degree d d d with some set of s s s coefficients preassigned (the constant term being non-zero, if it is preassigned). Suppose that A A A is not a subset of F q [ x ℓ ] \mathbb{F}_q[x^\ell] F q [ x ℓ ] for any ℓ > 1 \ell>1 ℓ > 1 . If q = p h q=p^h q = p h for some prime p > d p>d p > d and s ≤ d − 1 s\le d-1 s ≤ d − 1 , then, for any factor pattern λ \lambda λ , the number of polynomials with factor pattern λ \lambda λ is
T ( λ ) q d − s + 1 + O ( q d − s + 1 2 ) , T(\lambda)q^{d-s+1}+O(q^{d-s+\frac{1}{2}}), T ( λ ) q d − s + 1 + O ( q d − s + 2 1 ) , where the implied constant depends only on d d d .
In the case that λ = 1 ( d ) \lambda=1^{(d)} λ = 1 ( d ) this theorem counts the number of polynomials that split fully into linear terms.
Lemma 20. For fixed s ≤ k − 2 s\le k-2 s ≤ k − 2 , fixed prime p > k p>k p > k and large enough q = p h q=p^h q = p h , all x ∈ F q s x\in\mathbb{F}_q^s x ∈ F q s can be expressed as a sum of k k k elements from the set S + = { ( t , t 2 , … , t s ) : t ∈ F q } S_+=\{(t,t^2,\ldots,t^s):t\in\mathbb{F}_q\} S + = {( t , t 2 , … , t s ) : t ∈ F q } .
Proof. Consider an arbitrary element x = ( x 1 , … , x s ) ∈ F q s x=(x_1,\ldots,x_s)\in\mathbb{F}_q^s x = ( x 1 , … , x s ) ∈ F q s . We look for t 1 , … , t k ∈ F q t_1,\ldots,t_k\in\mathbb{F}_q t 1 , … , t k ∈ F q such that the equations
∑ i = 1 k t i j = x j , for all 1 ≤ j ≤ s (7) \sum_{i=1}^{k}t_i^j=x_j,\qquad\text{for all }1\le j\le s \tag*{(7)} i = 1 ∑ k t i j = x j , for all 1 ≤ j ≤ s (7)
hold. Let e j e_j e j denote the j j j th elementary symmetric function of the t i t_i t i , i.e., e 1 = t 1 + ⋯ + t k e_1=t_1+\cdots+t_k e 1 = t 1 + ⋯ + t k , e 2 = ∑ j 1 < j 2 t j 1 t j 2 e_2=\sum_{j_1<j_2}t_{j_1}t_{j_2} e 2 = ∑ j 1 < j 2 t j 1 t j 2 etc. The power sums and the elementary symmetric functions are related by the Newton identities which are invertible because p > k p>k p > k , so the equations in (7) determine the values of e 1 , … , e s e_1,\ldots,e_s e 1 , … , e s . Let A A A be the set of monic degree k k k polynomials in F q [ x ] \mathbb{F}_q[x] F q [ x ] with the first coefficients being the fixed values 1 , − e 1 , e 2 , … , ( − 1 ) s e s 1,-e_1,e_2,\ldots,(-1)^se_s 1 , − e 1 , e 2 , … , ( − 1 ) s e s . This is a set of polynomials with s + 1 ≤ k − 1 s+1\le k-1 s + 1 ≤ k − 1 coefficients fixed and in particular with the coefficient of x x x not fixed. Hence A ⊈ F q [ x ℓ ] A\not\subseteq\mathbb{F}_q[x^\ell] A ⊆ F q [ x ℓ ] for any ℓ > 1 \ell>1 ℓ > 1 and so by Theorem 19 the number of polynomials in A A A with factor pattern 1 ( k ) 1^{(k)} 1 ( k ) is T ( 1 ( k ) ) q k − s + O ( q k − s − 1 2 ) T(1^{(k)})q^{k-s}+O(q^{k-s-\frac{1}{2}}) T ( 1 ( k ) ) q k − s + O ( q k − s − 2 1 ) . For large enough q q q this is positive. Hence there is a polynomial r r r in A A A that splits into linear terms. The values of e 1 , … , e s e_1,\ldots,e_s e 1 , … , e s determine ∑ t i j \sum t_i^j ∑ t i j for j ≤ s j\le s j ≤ s . By definition of A A A the roots of r r r solve the equations in (7) , so there are k k k elements of S + S_+ S + that sum to x x x . □ \square □
For the limiting spectrum we rely on Weil’s bound of character sums and Katz’ equidistribution theorem. In particular, we use the following formulations of these results.
Theorem 21 (Weil bound [43 ] ). Let f ∈ F q [ x ] f \in\mathbb{F}_q[x] f ∈ F q [ x ] be a polynomial of degree d ≥ 1 d \ge1 d ≥ 1 with gcd ( d , q ) = 1 \gcd(d,q)=1 g cd( d , q ) = 1 and let χ \chi χ be a nontrivial additive character of F q \mathbb{F}_q F q . Then
∣ ∑ a ∈ F q χ ( f ( a ) ) ∣ ≤ ( d − 1 ) q \left|\sum_{a\in\mathbb{F}_q}\chi(f(a))\right| \le(d-1)\sqrt{q} a ∈ F q ∑ χ ( f ( a )) ≤ ( d − 1 ) q
Theorem 22 (Our version of Katz’ equidistribution theorem). Let d ≥ 3 d \ge3 d ≥ 3 be a fixed natural number and let p > 5 p > 5 p > 5 be a prime not dividing d d d . Choose an integer a ≥ 1 a \ge1 a ≥ 1 such that d ∣ p 2 a − 1 d \mid p^{2a}-1 d ∣ p 2 a − 1 and put Q = p 2 a Q=p^{2a} Q = p 2 a . Let q = Q r q=Q^r q = Q r , χ \chi χ a nontrivial additive character of F q \mathbb{F}_q F q and let P d 0 ( q ) ⊆ F q [ x ] \mathcal{P}_d^0(q) \subseteq\mathbb{F}_q[x] P d 0 ( q ) ⊆ F q [ x ] be the class of polynomials of degree d d d with zero constant term. As r → ∞ r \to\infty r → ∞ the empirical distribution associated with the multiset
{ q − 1 / 2 Re ( ∑ t ∈ F q χ ( f ( t ) ) ) : f ∈ P d 0 ( q ) } \left\{q^{-1/2}\operatorname{Re}\left(\sum_{t\in\mathbb{F}_q}\chi(f(t))\right): f\in\mathcal{P}_d^0(q)\right\} ⎩ ⎨ ⎧ q − 1/2 Re t ∈ F q ∑ χ ( f ( t )) : f ∈ P d 0 ( q ) ⎭ ⎬ ⎫ converges to a measure on [ 1 − d , d − 1 ] [1-d,d-1] [ 1 − d , d − 1 ] with infinite support.
This statement follows from deep algebraic geometric results by Katz [37 , 38 ] . The derivation of this precise form is done in Appendix § 7 . Using these results we prove Theorem 18.
Proof of Theorem 18. For k ≥ 5 k \ge5 k ≥ 5 and s = ⌊ k 2 ⌋ + 1 s=\left\lfloor\frac{k}{2}\right\rfloor+1 s = ⌊ 2 k ⌋ + 1 we have 3 ≤ s ≤ k − 2 3 \le s \le k-2 3 ≤ s ≤ k − 2 . Pick a prime p > k p>k p > k . Then p p p is a unit modulo s s s , so there is an a a a such that s ∣ p 2 a − 1 s\mid p^{2a}-1 s ∣ p 2 a − 1 . Consider the graph G q s G_q^s G q s for powers q q q of p 2 a p^{2a} p 2 a . Lemma 20 states that any element of F q \mathbb{F}_q F q can be written as the sum of at most k k k (leaving out the t = 0 t=0 t = 0 elements) elements of S S S , so G q s G_q^s G q s has diameter ≤ k \le k ≤ k for large enough q q q and hence α k ( G q s ) = 1 \alpha_k(G_q^s)=1 α k ( G q s ) = 1 . We show that the conditions of Lemma 15 are satisfied. For any fixed nontrivial character χ \chi χ of F q \mathbb{F}_q F q the eigenvalues of the Cayley graph are
λ a = ∑ u ∈ S χ ( a ⋅ u ) . \lambda_a=\sum_{u\in S}\chi(a\cdot u). λ a = u ∈ S ∑ χ ( a ⋅ u ) .
ranging over all a ∈ F q s a\in\mathbb{F}_q^s a ∈ F q s . As S S S consists of ± ( t , … , t s ) \pm(t,\ldots,t^s) ± ( t , … , t s ) and χ ( − x ) = χ ( x ) ‾ \chi(-x)=\overline{\chi(x)} χ ( − x ) = χ ( x ) this sum becomes 2 ∑ t ∈ F q Re χ ( a 1 t + a 2 t 2 + … + a s t s ) 2\sum_{t\in\mathbb{F}_q}\operatorname{Re}\chi(a_1t+a_2t^2+\ldots+a_st^s) 2 ∑ t ∈ F q Re χ ( a 1 t + a 2 t 2 + … + a s t s ) . Theorem 21 applies, because p > s ≥ deg f p>s\ge\deg f p > s ≥ deg f , so gcd ( p , deg f ) = 1 \gcd(p,\deg f)=1 g cd( p , deg f ) = 1 . Additionally, using χ ( 0 ) = 1 \chi(0)=1 χ ( 0 ) = 1 the eigenvalues for a ≠ 0 a\ne0 a = 0 fall in [ − 2 ( s − 1 ) q − 2 , 2 ( s − 1 ) q − 2 ] [-2(s-1)\sqrt{q}-2,2(s-1)\sqrt{q}-2] [ − 2 ( s − 1 ) q − 2 , 2 ( s − 1 ) q − 2 ] . The Perron eigenvalue, the degree, is 2 ( q − 1 ) 2(q-1) 2 ( q − 1 ) . Let μ q \mu_q μ q denote the ESD of the normalized adjacency matrix 1 2 ( q − 1 ) A ( G q s ) \frac{1}{\sqrt{2(q-1)}}A(G_q^s) 2 ( q − 1 ) 1 A ( G q s ) whose eigenvalues are denoted ξ a \xi_a ξ a . All the nontrivial normalized eigenvalues fall in the interval I = [ − 2 ( 1 + s ) , 2 ( s − 1 ) ] I=[-\sqrt{2}(1+s),\sqrt{2}(s-1)] I = [ − 2 ( 1 + s ) , 2 ( s − 1 )] . For the inertia-type bound we are interested in r ( ξ a ) r(\xi_a) r ( ξ a ) for all r ∈ S k = { f ∈ P k : ∥ f ∥ ∞ , I = 1 } r\in S_k=\{f\in P_k:\|f\|_{\infty,I}=1\} r ∈ S k = { f ∈ P k : ∥ f ∥ ∞ , I = 1 } . We have ξ 0 = ( 1 + o ( 1 ) ) 2 q \xi_0=(1+o(1))\sqrt{2q} ξ 0 = ( 1 + o ( 1 )) 2 q and because the order n n n is q s q^s q s , we have
1 n sup r ∈ S k ∣ r ( ξ 0 ) ∣ = O ( 1 + ( 2 q ) k / 2 n ) = o ( 1 ) . \frac{1}{n}\sup_{r\in S_k}|r(\xi_0)|=O\left(\frac{1+(2q)^{k/2}}{n}\right)=o(1). n 1 r ∈ S k sup ∣ r ( ξ 0 ) ∣ = O ( n 1 + ( 2 q ) k /2 ) = o ( 1 ) .
We conclude that sup r ∈ S k ∫ R ∣ r ∣ d μ q → 0 \sup_{r\in S_k}\int_{\mathbb{R}} |r|\,d\mu_q \to0 sup r ∈ S k ∫ R ∣ r ∣ d μ q → 0 . For the a ∈ F q s a\in\mathbb{F}_q^s a ∈ F q s with a s ≠ 0 a_s\ne0 a s = 0 the polynomial p a = a 1 t + … + a s t s p_a=a_1t+\ldots+a_st^s p a = a 1 t + … + a s t s is in P s 0 ( q ) \mathcal{P}_s^0(q) P s 0 ( q ) . The associated eigenvalue ξ a \xi_a ξ a is equal to
2 2 ( q − 1 ) ∑ t ∈ F q × ℜ χ ( p a ( t ) ) . \frac{2}{\sqrt{2(q-1)}}\sum_{t\in\mathbb{F}_q^\times}\Re\chi(p_a(t)). 2 ( q − 1 ) 2 t ∈ F q × ∑ ℜ χ ( p a ( t )) .
As q → ∞ q\to\infty q → ∞ the distribution of these eigenvalues differs by o ( 1 ) o(1) o ( 1 ) from
{ 2 q − 1 / 2 ℜ ( ∑ t ∈ F q χ ( f ( t ) ) ) : f ∈ P s 0 ( q ) } , \left\{\sqrt{2}q^{-1/2}\Re\left(\sum_{t\in\mathbb{F}_q}\chi(f(t))\right):f\in\mathcal{P}_s^0(q)\right\}, ⎩ ⎨ ⎧ 2 q − 1/2 ℜ t ∈ F q ∑ χ ( f ( t )) : f ∈ P s 0 ( q ) ⎭ ⎬ ⎫ ,
which converges to some measure μ \mu μ with infinite support (contained in I I I ) by Theorem 22. The contribution of the eigenvalues with a s = 0 a_s=0 a s = 0 goes to zero. This was already shown for the Perron eigenvalue. The remaining eigenvalues lie in I I I , so ∣ r ( ξ ) ∣ ≤ 1 |r(\xi)|\le1 ∣ r ( ξ ) ∣ ≤ 1 for r ∈ S k r\in S_k r ∈ S k . The eigenvalues with a s = 0 a_s=0 a s = 0 form a 1 q \frac{1}{q} q 1 fraction of all eigenvalues, so their contribution to ∫ R ∣ r ∣ d μ q \int_{\mathbb{R}}|r|\,d\mu_q ∫ R ∣ r ∣ d μ q goes to zero. Therefore the whole ESD converges to μ \mu μ uniformly over r r r , i.e.,
sup r ∈ S k ∣ ∫ R ∣ r ∣ d μ q − ∫ I ∣ r ∣ d μ ∣ → 0. \sup_{r\in S_k}\left|\int_{\mathbb{R}}|r|\,d\mu_q-\int_I|r|\,d\mu\right|\to0. r ∈ S k sup ∫ R ∣ r ∣ d μ q − ∫ I ∣ r ∣ d μ → 0.
This means that all conditions of Lemma 15 are satisfied and hence there is an ε > 0 \varepsilon>0 ε > 0 , such that the inertia-type bound is at least ε q s \varepsilon q^s ε q s .
Concluding remarks
It is now clear that the weighted inertia bound, and even more so the inertia-type bound, can be far from tight and that this is not an exception, but happens for almost all graphs of the right density. Still, there are examples where these bounds are effective in Erdős-Ko-Rado results [20 ] and coding theory [6 ] . Understanding what properties of the graph or spectrum make the inertia bound perform “well” remains an open problem. In this process one may also ask if current separation results are really best possible.
For k k k -independence specifically, we do not claim that our separation results are optimal. An obvious example where improvement should be possible is in Theorem 14, which does not give a significantly better lower bound for k = 2 k=2 k = 2 compared to k = 3 k=3 k = 3 . Note further that our results give separation for dense graphs and graph powers. For sparse graphs, such as sparse random graphs or random regular graphs the k k k -independence number is larger, see e.g. [14 , 15 ] , but it also seems likely that the weighted inertia bound performs worse. Currently, it is unknown how much worse the weighted inertia bound (and also the inertia-type bound) will be for sparse graphs if we cannot guarantee C 4 C_4 C 4 -freeness.
There are more lower bounds on the inertia(-type) bound. It is known that the quantum independence number α q ( G ) \alpha_q(G) α q ( G ) , and even the quantum k k k -independence number α k q ( G ) : = α q ( G k ) \alpha_{kq}(G):=\alpha_q(G^k) α k q ( G ) := α q ( G k ) , is in between the independence number and the inertia bounds, for the definition and this result see [52 ] . Any graph with separation between α ( G ) \alpha(G) α ( G ) and α q ( G ) \alpha_q(G) α q ( G ) also gives separation between α ( G ) \alpha(G) α ( G ) and ν ≥ 0 ( G ) \nu_{\ge0}(G) ν ≥ 0 ( G ) . However, it is difficult to determine α q \alpha_q α q and hence to give large separation between α ( G ) \alpha(G) α ( G ) and α q ( G ) \alpha_q(G) α q ( G ) or α k ( G ) \alpha_k(G) α k ( G ) and α k q ( G ) \alpha_{kq}(G) α k q ( G ) . In particular, it is known that α q = α \alpha_q = \alpha α q = α if α ( G ) ≤ 2 \alpha(G) \le2 α ( G ) ≤ 2 . Therefore the results in Theorems 14 and 18 and Corollary 17 also give separation between the inertia(-type) bound and α k q ( G ) \alpha_{kq}(G) α k q ( G ) . Our results do not help in identifying which graphs have (large) separation between the ( k ) (k) ( k ) -independence number and the corresponding quantum parameter, but we know that those graphs must also have an inertia(-type) bound that is far from tight.
The research of this paper was assisted by the use of Gemini and ChatGPT. Specifically, the ideas for considering random graphs, random Cayley graphs and pseudorandom Cayley graphs were conceived by the authors, but specific proofs and constructions for the latter two were suggested by AI. The working out of details of the proof in § 2.3 was assisted by ChatGPT 5.5. More notably, the proof method of Lemma 8 was suggested by Gemini 3.1. Additionally, § 3.2 and Appendix § 7 were greatly supported by ChatGPT 5.5 and 5.6. The construction used in Theorem 18 was suggested by ChatGPT 5.5 based on our specific suggestions for such a construction. ChatGPT 5.5 and 5.6 were consequently used for understanding the algebraic geometric background of these constructions. These tools were also used throughout to find literature, typos and small mistakes. However, all writing in this paper was done by the authors.
Acknowledgements
Aida Abiad and Nils van de Berg are supported by NWO (Dutch Research Council) through the grant VI.Vidi.213.085 (grant ID https://doi.org/10.61686/CSWNV56135 ). Sam Mattheus is supported by postdoctoral fellowships 1267923N and 12A0J27N from the Research Foundation Flanders (FWO). This research was partially supported by the FWO Scientific Research Communities: Graphs, Association schemes and Geometries: structures, algorithms and computation (W003324N) and Finite Geometry, Coding Theory and Cryptography (W0.032.24N). The authors thank Harper Reijnders for useful discussions on § 2 and Prof. Emmanuel Kowalski for giving feedback on the arithmetic geometry content of the appendix. Part of this work was done while the first author was visiting the Simons Institute for the Theory of Computing at UC Berkeley.
Appendix: Proof of Theorem 22
Recall that we want to prove the following.
Theorem 22 (Our version of Katz’ equidistribution theorem). Let d ≥ 3 d \ge3 d ≥ 3 be a fixed natural number and let p > 5 p > 5 p > 5 be a prime not dividing d d d . Choose an integer a ≥ 1 a \ge1 a ≥ 1 such that d ∣ p 2 a − 1 d \mid p^{2a} - 1 d ∣ p 2 a − 1 and put Q = p 2 a Q = p^{2a} Q = p 2 a . Let q = Q r q = Q^r q = Q r , χ \chi χ a nontrivial additive character of F q \mathbb{F}_q F q and let P d 0 ( q ) ⊆ F q [ x ] \mathcal{P}^{0}_{d}(q) \subseteq\mathbb{F}_q[x] P d 0 ( q ) ⊆ F q [ x ] be the class of polynomials of degree d d d with zero constant term. As r → ∞ r \to\infty r → ∞ the empirical distribution associated with the multiset
{ q − 1 / 2 Re ( ∑ t ∈ F q χ ( f ( t ) ) ) : f ∈ P d 0 ( q ) } \left\{q^{-1/2}\operatorname{Re}\left(\sum_{t\in\mathbb{F}_q}\chi(f(t))\right): f\in\mathcal{P}^{0}_{d}(q)\right\} ⎩ ⎨ ⎧ q − 1/2 Re t ∈ F q ∑ χ ( f ( t )) : f ∈ P d 0 ( q ) ⎭ ⎬ ⎫ converges to a measure on [ 1 − d , d − 1 ] [1-d,d-1] [ 1 − d , d − 1 ] with infinite support.
This result nearly follows from [26 ] , specifically Section 2 up to Theorem 3 where Entin states the following as a special case of Katz’ results.
Theorem 23 ([26 Theorem 3] ). Let d ≥ 3 d \ge3 d ≥ 3 be a fixed natural number and assume F q \mathbb{F}_q F q is a field whose characteristic is a fixed prime > 5 > 5 > 5 that does not divide d d d . Then as q → ∞ q \to\infty q → ∞ the family { Θ f } f ∈ P d \{\Theta_f\}_{f\in\mathcal{P}_d} { Θ f } f ∈ P d becomes equidistributed in the space of conjugacy classes of some Lie group SU ( d − 1 ) ⊂ G ⊂ U ( d − 1 ) \operatorname{SU}(d-1) \subset G \subset\operatorname{U}(d-1) SU ( d − 1 ) ⊂ G ⊂ U ( d − 1 ) with the measure induced from the Haar measure on G G G .
However, this statement is not precise. The group G G G may change as q q q varies. This can be resolved by passing to field extensions of F Q \mathbb{F}_Q F Q . We show this essential step in Lemma 26. Pasting this result into Entin’s statement does not give a satisfying rigorous proof. Instead, we provide a more complete argument. We have aimed to write this proof so it can be understood with as little algebraic geometric background as possible. However, the argument uses some deep results in arithmetic geometry. We have tried to translate these to our (simpler) setting. For a complete understanding the reader should be familiar with representation theory, Haar measures, the topology of linear groups and the fundamental groups of schemes.
We first state the two deep results as written by Katz and Sarnak that we will be using.
Theorem 24 ([37 Theorem 3.9.2] for n = 1 n = 1 n = 1 , p > 5 p > 5 p > 5 ). Let k k k be a finite field with characteristic p > 5 p > 5 p > 5 and ℓ ≠ p \ell\ne p ℓ = p both prime, let ψ : k → Q ‾ ℓ \psi: k \to\overline{\mathbb{Q}}_{\ell} ψ : k → Q ℓ be a nontrivial additive character and let d d d be an integer such that gcd ( p , d ) = 1 \gcd(p,d) = 1 g cd( p , d ) = 1 . Let E E E be a finite field extension of k k k and let D ( d , E ) ⊆ E [ x ] D(d,E) \subseteq E[x] D ( d , E ) ⊆ E [ x ] denote the scheme of polynomials of degree d d d over E E E . Then the lisse, pure of weight zero sheaf M ( d , ψ ) M(d,\psi) M ( d , ψ ) of rank d − 1 d-1 d − 1 on D ( d , E ) D(d,E) D ( d , E ) with trace function given by
tr ρ ( Frob E , f ∣ M ( d , ψ ) ) = − 1 ∣ E ∣ 1 / 2 ∑ t ∈ E ψ ( f ( t ) ) \operatorname{tr}\rho(\operatorname{Frob}_{E,f} \mid M(d,\psi)) = -\frac{1}{|E|^{1/2}}\sum_{t\in E}\psi(f(t)) tr ρ ( Frob E , f ∣ M ( d , ψ )) = − ∣ E ∣ 1/2 1 t ∈ E ∑ ψ ( f ( t )) for f ∈ D ( d , E ) f \in D(d,E) f ∈ D ( d , E ) has geometric monodromy group G g e o m ( Q ‾ ℓ ) G_{\mathrm{geom}}(\overline{\mathbb{Q}}_{\ell}) G geom ( Q ℓ ) contains SL ( d − 1 , Q ‾ ℓ ) \operatorname{SL}(d-1,\overline{\mathbb{Q}}_{\ell}) SL ( d − 1 , Q ℓ ) .
:::`
For a lisse sheaf on scheme X X X , the geometric monodromy group is the Zariski closure of ρ ( π 1 ( X / k ‾ ) ) \rho(\pi_1(X/\overline{k})) ρ ( π 1 ( X / k )) where ρ \rho ρ is the representation associated to the sheaf, so in our case the group lives in G L ( d − 1 , Q ‾ ℓ ) GL(d-1,\overline{\mathbb{Q}}_\ell) G L ( d − 1 , Q ℓ ) . We note that the theorem statement is also true when restricting the sheaf to the set of polynomials with zero constant coefficient. This can be seen as [26 Theorem 3] applies to this same set of polynomials with zero coefficient.
Theorem 25. [38 Theorem 9.2.6] for n = 1 n=1 n = 1 , p > 5 p>5 p > 5 . Let k k k be a finite field, X / k X/k X / k a smooth, geometrically connected scheme, ℓ \ell ℓ a prime number invertible in k k k , ι \iota ι a field embedding of Q ‾ ℓ \overline{\mathbb{Q}}_\ell Q ℓ into C \mathbb{C} C , and F \mathcal{F} F a lisse Q ‾ ℓ \overline{\mathbb{Q}}_\ell Q ℓ -sheaf on X X X of rank r ≥ 1 r\geq1 r ≥ 1 corresponding to an r r r -dimensional continuous Q ‾ ℓ \overline{\mathbb{Q}}_\ell Q ℓ -representation ρ \rho ρ of π 1 ( X / k ) \pi_1(X/k) π 1 ( X / k ) . Assume that F \mathcal{F} F is ι \iota ι -pure of weight zero, and that ρ ( π 1 ) ⊆ G g e o m ( Q ‾ ℓ ) \rho(\pi_1)\subseteq G_{\mathrm{geom}}(\overline{\mathbb{Q}}_\ell) ρ ( π 1 ) ⊆ G geom ( Q ℓ ) . Denote by K K K a maximal compact subgroup of G g e o m ( C ) G_{\mathrm{geom}}(\mathbb{C}) G geom ( C ) . Then the Frobenius conjugacy classes θ ( E , x ) \theta(E,x) θ ( E , x ) are equidistributed in the space of conjugacy classes of K K K as ∣ E ∣ → ∞ |E|\to\infty ∣ E ∣ → ∞ , in the sense that for any continuous C \mathbb{C} C -valued function g g g that is constant on conjugacy classes
1 ∣ X ( E ) ∣ ∑ x ∈ X ( E ) g ( θ ( E , x ) ) → ∫ K g d μ H a a r . \frac{1}{|X(E)|}\sum_{x\in X(E)}g(\theta(E,x))\to\int_K g\,d\mu_{\mathrm{Haar}}. ∣ X ( E ) ∣ 1 x ∈ X ( E ) ∑ g ( θ ( E , x )) → ∫ K g d μ Haar .
In order to use the equidistribution theorem we need to show the following.
Lemma 26. The condition ρ ( π 1 ) ⊆ G g e o m \rho(\pi_1)\subseteq G_{\mathrm{geom}} ρ ( π 1 ) ⊆ G geom holds in the setting of Theorem 25 when k = F Q k=\mathbb{F}_Q k = F Q , X = P 0 X=\mathcal{P}^0 X = P 0 and F = M 0 ( d , ψ ) \mathcal{F}=\mathcal{M}^0(d,\psi) F = M 0 ( d , ψ ) , the sheaf from Theorem 24 .
Proof. Let f a ( t ) = b t d f_a(t)=bt^d f a ( t ) = b t d for b ∈ F Q × b\in\mathbb{F}_Q^\times b ∈ F Q × be a map in X ( F Q ) X(\mathbb{F}_Q) X ( F Q ) . We will show that there is a choice of b b b such that B b = ρ ( F r o b F Q , f b ) B_b=\rho(Frob_{\mathbb{F}_Q,f_b}) B b = ρ ( F r o b F Q , f b ) (a d − 1 d-1 d − 1 dimensional matrix) has det B b = 1 \det B_b=1 det B b = 1 . Given this, we know that B b ∈ S L ( d − 1 ) ⊆ G g e o m B_b\in SL(d-1)\subseteq G_{\mathrm{geom}} B b ∈ S L ( d − 1 ) ⊆ G geom by Theorem 24 . As X X X is connected, there is a short exact sequence
1 ⟶ π 1 ( X / k ‾ ) ⟶ π 1 ( X / k ) → τ Gal ( k ‾ / k ) ⟶ 1 , 1\longrightarrow\pi_1(X/\overline{k})\longrightarrow\pi_1(X/k)\xrightarrow{\tau}\operatorname{Gal}(\overline{k}/k)\longrightarrow1, 1 ⟶ π 1 ( X / k ) ⟶ π 1 ( X / k ) τ Gal ( k / k ) ⟶ 1 ,
see e.g. [48 ] . In our case k = F Q k=\mathbb{F}_Q k = F Q and it is known that the Galois group is topologically generated by the image of a Frobenius map [42 ] . By exactness and compactness this means that π 1 ( X / F Q ) \pi_1(X/\mathbb{F}_Q) π 1 ( X / F Q ) is topologically generated by π 1 ( X / F ‾ Q ) \pi_1(X/\overline{\mathbb{F}}_Q) π 1 ( X / F Q ) and F r o b F Q , f b Frob_{\mathbb{F}_Q,f_b} F r o b F Q , f b . Applying ρ \rho ρ and noting that B b B_b B b is in the topologically closed G g e o m G_{\mathrm{geom}} G geom then implies that ρ ( π 1 ( X / F Q ) ) ⊆ G g e o m \rho(\pi_1(X/\mathbb{F}_Q))\subseteq G_{\mathrm{geom}} ρ ( π 1 ( X / F Q )) ⊆ G geom .
All that is left is to find an b b b with det B b = 1 \det B_b=1 det B b = 1 . We identify the eigenvalues of B b B_b B b by considering tr B b r \operatorname{tr} B_b^r tr B b r . Note that F r o b F Q , f b r = F r o b F Q r , f b Frob_{\mathbb{F}_Q,f_b}^r=Frob_{\mathbb{F}_{Q^r},f_b} F r o b F Q , f b r = F r o b F Q r , f b , so that B b r = ρ ( F r o b F Q r , f b ) B_b^r=\rho(Frob_{\mathbb{F}_{Q^r},f_b}) B b r = ρ ( F r o b F Q r , f b ) . By Theorem 24 this has trace
− 1 Q r / 2 ∑ t ∈ F Q r ψ r ( b t d ) -\frac{1}{Q^{r/2}}\sum_{t\in\mathbb{F}_{Q^r}}\psi_r(bt^d) − Q r /2 1 t ∈ F Q r ∑ ψ r ( b t d )
where ψ r = ψ ∘ tr F Q r / F Q \psi_r=\psi\circ\operatorname{tr}_{\mathbb{F}_{Q^r}/\mathbb{F}_Q} ψ r = ψ ∘ tr F Q r / F Q is the lift of ψ \psi ψ to F Q r \mathbb{F}_{Q^r} F Q r . Due to d ∣ Q − 1 d\mid Q-1 d ∣ Q − 1 we know that F Q \mathbb{F}_Q F Q contains all d d d roots of unity. Therefore the calculation of − ∑ x ψ r ( b x e ) -\sum_x\psi_r(bx^e) − ∑ x ψ r ( b x e ) in the proof of [37 Theorem 6.8.34] applies and the trace can be rewritten using a nontrivial multiplicative character η \eta η on F Q \mathbb{F}_Q F Q .
− Q − r / 2 ∑ η ≠ 1 , η d = 1 η ‾ r ( b ) ∑ y η r ( y ) ψ r ( y ) . (8) -Q^{-r/2}\sum_{\substack{\eta\ne1,\ \eta^d=1}}\overline{\eta}_r(b)\sum_y\eta_r(y)\psi_r(y). \tag*{(8)} − Q − r /2 η = 1 , η d = 1 ∑ η r ( b ) y ∑ η r ( y ) ψ r ( y ) . (8)
By definition we have
η r ( b ) = η ∘ N F Q r / F Q ( b ) = η ( b r ) = η ( b ) r , (9) \eta_r(b)=\eta\circ N_{\mathbb{F}_{Q^r}/\mathbb{F}_Q}(b)=\eta(b^r)=\eta(b)^r, \tag*{(9)} η r ( b ) = η ∘ N F Q r / F Q ( b ) = η ( b r ) = η ( b ) r , (9)
because b ∈ F Q b \in\mathbb{F}_Q b ∈ F Q . In addition, the Hasse–Davenport lifting relation [34 ] says that
− ∑ y ∈ F Q r η r ( y ) ψ r ( y ) = ( − 1 ) r ( ∑ y ∈ F Q η ( y ) ψ ( y ) ) r -\sum_{y\in\mathbb{F}_{Q^r}} \eta_r(y)\psi_r(y)=(-1)^r\left(\sum_{y\in\mathbb{F}_Q}\eta(y)\psi(y)\right)^r − y ∈ F Q r ∑ η r ( y ) ψ r ( y ) = ( − 1 ) r y ∈ F Q ∑ η ( y ) ψ ( y ) r
Plugging this into (8) gives
tr B r = ∑ η ≠ 1 , η d = 1 ( − Q − 1 / 2 η ‾ ( b ) ∑ y η ( y ) ψ ( y ) ) r (10) \operatorname{tr} B^r=\sum_{\substack{\eta\ne1,\eta^d=1}}\left(-Q^{-1/2}\overline{\eta}(b)\sum_y\eta(y)\psi(y)\right)^r \tag*{(10)} tr B r = η = 1 , η d = 1 ∑ ( − Q − 1/2 η ( b ) y ∑ η ( y ) ψ ( y ) ) r (10)
This identifies the eigenvalues of B B B as λ η = − Q − 1 / 2 η ‾ ( b ) ∑ y η ( y ) ψ ( y ) \lambda_\eta=-Q^{-1/2}\overline{\eta}(b)\sum_y\eta(y)\psi(y) λ η = − Q − 1/2 η ( b ) ∑ y η ( y ) ψ ( y ) . Using η ( b ) η − 1 ( b ) = 1 \eta(b)\eta^{-1}(b)=1 η ( b ) η − 1 ( b ) = 1 and the identity of Gauss sums [35 ] we find that λ η λ η − 1 = η ( − 1 ) \lambda_\eta\lambda_{\eta^{-1}}=\eta(-1) λ η λ η − 1 = η ( − 1 ) . For odd d d d we have η ( − 1 ) = 1 \eta(-1)=1 η ( − 1 ) = 1 and we can pair up all eigenvalues, so the determinant is
∏ η ≠ 1 , η d = 1 λ η = 1. \prod_{\substack{\eta\ne1,\eta^d=1}}\lambda_\eta=1. η = 1 , η d = 1 ∏ λ η = 1.
For even d d d we get one eigenvalue that is not paired. This corresponds to the nontrivial character η 2 \eta_2 η 2 with η 2 2 = 1 \eta_2^2=1 η 2 2 = 1 . By the Gauss sum identity we have λ η 2 2 = η 2 ( − 1 ) \lambda_{\eta_2}^2=\eta_2(-1) λ η 2 2 = η 2 ( − 1 ) . As Q Q Q is an odd square we find that − 1 -1 − 1 is a square in F Q \mathbb{F}_Q F Q , so η 2 ( − 1 ) = 1 \eta_2(-1)=1 η 2 ( − 1 ) = 1 . Hence λ η 2 ∈ { − 1 , 1 } \lambda_{\eta_2}\in\{-1,1\} λ η 2 ∈ { − 1 , 1 } . This value depends on b b b . In particular, we can pair up the inverse pairs to see there is an α ∈ { − 1 , 1 } \alpha\in\{-1,1\} α ∈ { − 1 , 1 } independent of b b b such that det B b = α η 2 ( b ) \det B_b=\alpha\eta_2(b) det B b = α η 2 ( b ) . By taking b b b to be a square or non-square we can flip the sign of the determinant. Hence, we can choose a b b b such that det ρ ( Frob F Q , f b ) = 1 \det\rho(\operatorname{Frob}_{\mathbb{F}_Q,f_b})=1 det ρ ( Frob F Q , f b ) = 1 .
Now we can show Theorem 22. We take k = F Q k=\mathbb{F}_Q k = F Q (so that extensions E = F q E=\mathbb{F}_q E = F q ), X ( F q ) = P d 0 ( q ) X(\mathbb{F}_q)=\mathcal{P}^{0}_d(q) X ( F q ) = P d 0 ( q ) and F = M 0 ( d , χ ) \mathcal{F}=\mathcal{M}^{0}(d,\chi) F = M 0 ( d , χ ) . Due to Lemma 26 and our comments after Theorem 24 all the necessary conditions of Theorem 25 are satisfied. The Frobenius conjugacy class θ ( E , f ) \theta(E,f) θ ( E , f ) , defined in 9.2.4 in [38 ] , is exactly the conjugacy class of K K K which is contained in the (semisimple part of the) conjugacy class of ι ρ ( Frob E , f ∣ F ) \iota\rho(\operatorname{Frob}_{E,f}\mid\mathcal{F}) ι ρ ( Frob E , f ∣ F ) . Importantly for us, this implies that tr θ ( E , f ) = − q − 1 / 2 ∑ t ∈ F q χ ( f ( t ) ) \operatorname{tr}\theta(E,f)=-q^{-1/2}\sum_{t\in\mathbb{F}_q}\chi(f(t)) tr θ ( E , f ) = − q − 1/2 ∑ t ∈ F q χ ( f ( t )) . For any continuous function g g g , the composition g ∘ ( − Re tr ) g\circ(-\operatorname{Re}\operatorname{tr}) g ∘ ( − Re tr ) is continuous and constant on conjugacy classes and thus Theorem 25 states that there is a compact subgroup K K K of G g e o m ( C ) G_{\mathrm{geom}}(\mathbb{C}) G geom ( C ) such that
1 q d − 1 ( q − 1 ) ∑ f ∈ P d 0 ( q ) g ∘ Re ( 1 q 1 / 2 ∑ t ∈ F q χ ( f ( t ) ) ) → ∫ K g ∘ ( − Re tr ) d ν H a a r . \frac{1}{q^{d-1}(q-1)}\sum_{f\in\mathcal{P}^{0}_d(q)}g\circ\operatorname{Re}\left(\frac{1}{q^{1/2}}\sum_{t\in\mathbb{F}_q}\chi(f(t))\right)\to\int_K g\circ(-\operatorname{Re}\operatorname{tr})\,d\nu_{\mathrm{Haar}}. q d − 1 ( q − 1 ) 1 f ∈ P d 0 ( q ) ∑ g ∘ Re q 1/2 1 t ∈ F q ∑ χ ( f ( t )) → ∫ K g ∘ ( − Re tr ) d ν Haar .
From Theorem 24 we get that SL ( d − 1 , Q ‾ ℓ ) ⊆ G g e o m ( Q ‾ ℓ ) ⊆ GL ( d − 1 , Q ‾ ℓ ) \operatorname{SL}(d-1,\overline{\mathbb{Q}}_\ell)\subseteq G_{\mathrm{geom}}(\overline{\mathbb{Q}}_\ell)\subseteq\operatorname{GL}(d-1,\overline{\mathbb{Q}}_\ell) SL ( d − 1 , Q ℓ ) ⊆ G geom ( Q ℓ ) ⊆ GL ( d − 1 , Q ℓ ) . The embedding ι \iota ι , then gives SL ( d − 1 , C ) ⊆ G g e o m ( C ) ⊆ GL ( d − 1 , C ) \operatorname{SL}(d-1,\mathbb{C})\subseteq G_{\mathrm{geom}}(\mathbb{C})\subseteq\operatorname{GL}(d-1,\mathbb{C}) SL ( d − 1 , C ) ⊆ G geom ( C ) ⊆ GL ( d − 1 , C ) . Maximal compact subgroups of these linear groups are conjugations of SU ( d − 1 ) \operatorname{SU}(d-1) SU ( d − 1 ) and U ( d − 1 ) \operatorname{U}(d-1) U ( d − 1 ) , so K K K can be chosen to lie between these unitary groups. The function Φ : K → R \Phi:K\to\mathbb{R} Φ : K → R that maps M M M to − Re tr M -\operatorname{Re}\operatorname{tr}M − Re tr M is continuous. Then μ = Φ ∗ ν H a a r \mu=\Phi_*\nu_{\mathrm{Haar}} μ = Φ ∗ ν Haar is the probability measure that assigns to open I ⊆ R I\subseteq\mathbb{R} I ⊆ R the value μ ( I ) = ν ( Φ − 1 ( I ) ) \mu(I)=\nu(\Phi^{-1}(I)) μ ( I ) = ν ( Φ − 1 ( I )) . As K ⊆ U ( d − 1 ) K\subseteq\operatorname{U}(d-1) K ⊆ U ( d − 1 ) , this measure is supported on [ 1 − d , d − 1 ] [1-d,d-1] [ 1 − d , d − 1 ] . For any y ∈ Im Φ y\in\operatorname{Im}\Phi y ∈ Im Φ , take an open neighbourhood J y J_y J y of y y y . By continuity Φ − 1 ( J y ) \Phi^{-1}(J_y) Φ − 1 ( J y ) is a non-empty open subset of K K K and hence the Haar measure, defined on a compact group, assigns positive measure to it. Hence μ ( J y ) = ν ( Φ − 1 ( J y ) ) > 0 \mu(J_y) = \nu(\Phi^{-1}(J_y)) > 0 μ ( J y ) = ν ( Φ − 1 ( J y )) > 0 . This holds for all y y y , so μ \mu μ has support Im Φ \operatorname{Im}\Phi Im Φ .
For every θ ∈ R \theta\in\mathbb{R} θ ∈ R , the matrix U θ = diag ( e i θ , e − i θ , 1 , … , 1 ) U_\theta= \operatorname{diag}(e^{i\theta}, e^{-i\theta}, 1, \ldots, 1) U θ = diag ( e i θ , e − i θ , 1 , … , 1 ) belongs to S U ( d − 1 ) ⊆ K SU(d-1) \subseteq K S U ( d − 1 ) ⊆ K , and Φ ( U θ ) = − ( d − 3 + 2 cos θ ) \Phi(U_\theta) = -(d - 3 + 2\cos\theta) Φ ( U θ ) = − ( d − 3 + 2 cos θ ) . Thus supp μ \operatorname{supp}\mu supp μ contains the nondegenerate interval [ 1 − d , 5 − d ] [1-d, 5-d] [ 1 − d , 5 − d ] , and in particular is infinite. We conclude that the empirical distribution of
{ q − 1 / 2 ℜ ( ∑ t ∈ F q χ ( f ( t ) ) ) : f ∈ P d 0 ( q ) } \left\{q^{-1/2}\Re\left(\sum_{t\in\mathbb{F}_q}\chi(f(t))\right): f\in\mathcal{P}_d^0(q)\right\} ⎩ ⎨ ⎧ q − 1/2 ℜ t ∈ F q ∑ χ ( f ( t )) : f ∈ P d 0 ( q ) ⎭ ⎬ ⎫
converges to a measure μ \mu μ with infinite support.