Introduction to polynomial method

(The following is a blog-friendly version of Chapter 7 of my PhD thesis, which is an introduction to the so-called polynomial method.)

The polynomial method is an umbrella term for different techniques involving polynomials which have been used to solve several problems in finite geometry, discrete geometry, extremal combinatorics and additive number theory. One of the general philosophies behind this method is to associate a set of polynomials (possibly a single polynomial), to a combinatorial object that we want to study, and then use some properties of these polynomials to describe the combinatorial object. For a concrete example, let us go through Koornwinder’s proof of the absolute bound on equiangular lines.

A set of lines in the Euclidean space \mathbb{R}^n through the origin (or any other fixed point) is called equiangular if the angle between every pair of distinct lines in the set is the same. For example, joining the opposite vertices of a regular hexagon in the plane \mathbb{R}^2, we get three equiangular lines.

At most how many equiangular lines can there be in \mathbb{R}^n?

This question was addressed by Gerzon (as reported by Lemmens and Seidel) who proved that there are at most n+1 equiangular lines in \mathbb{R}^n. Thus in particular, the regular hexagon example gives us the maximum possible equiangular lines in \mathbb{R}^2. But in general this bound is not sharp. In 1976, Koornwinder gave an “almost trivial proof” of Gerzon’s bound by giving a bijective correspondence between the set of equiangular lines in \mathbb{R}^n and a linearly independent set of polynomials lying in an {n+1 \choose 2} dimensional vector  space. This correspondence is as follows. Let L_1, \dots , L_k be k equiangular lines in \mathbb{R}^n and let u_1, \dots, u_k be unit vectors on these lines, chosen arbitrarily. Then we have \langle u_i,u_j \rangle^2 = \alpha for i \neq j where \alpha is a fixed real number in the interval [0,1). For i \in \{1, \dots, k\} define f_i \in \mathbb{R}[t_1, \dots, t_n] by f_i(t_1, \dots, t_n) = \langle u_i, (t_1, \dots, t_n) \rangle^2 - \alpha^2 (t_1^2 + \dots + t_n^2). Now since f_i(u_j) = 0 for all i \neq j and f_i(u_i) = 1 -\alpha^2 \neq 0, it is easy to see that f_1, \dots, f_k are linearly independent polynomials in the vector space \mathbb{R}[t_1, \dots, t_n]. As these polynomials lie in the {n + 1 \choose 2} dimensional subspace spanned by the monomial set \{t_i t_j : 1 \leq i < j \leq k\}, we get k \leq \binom{n + 1}{2}.

The argument above can also be seen as an example of the linear algebra method in combinatorics, which has been discussed in much detail in the influential (unfinished) manuscript of Babai and Frankl, and more recently in the beautiful book by Matoušek.

Another important way of using polynomials is to capture the combinatorial object via zeros of polynomials (or in general, algebraic varieties). One of the earliest examples here is the determination of the minimum size of an affine blocking set by Jamison in 1977. The problem is to find the minimum number of points required to “block” every hyperplane of the affine space \mathbb{F}_q^n. Clearly n(q - 1) + 1 points suffice (by taking all points that lie on one of the n axes), but can we do better? Jamison proved that we cannot, and his polynomial method proof can be sketched as follows: (a) first consider the dual problem, which is equivalent to finding the minimum number of hyperplanes required to cover all points of \mathbb{F}_q^n except the origin, (b) then identify \mathbb{F}_q^n with the finite field \mathbb{F}_q^n, (c) finally associate each hyperplane with the minimal polynomial over \mathbb{F}_q^n that vanishes on the hyperplane to show (using the theory of linearized polynomials) that if the number of hyperplanes is less than n(q - 1) + 1, then the polynomial t^{q^n - 1} - 1 = \prod_{\alpha \in \mathbb{F}_q^\times} (t - \alpha) does not divide the product of these polynomials corresponding to the hyperplanes. This technique of using polynomials over finite fields to solve finite geometrical problems came to be known as the “Jamison method” and it saw several applications (see for example this and this).

Brouwer and Schrijver gave another proof of Jamison’s theorem where they also started by considering the dual problem of hyperplane coverings but then proceeded by a much simpler argument involving multivariate polynomials over finite fields. Their approach was in fact quite similar to Chevalley’s proof of the famous Chevalley-Warning theorem  using reduced polynomials. We will see in Chapters 8 and 9 how both of these results are linked together by the notion of grid reduction, and in particular by the Lemma that a polynomial \mathbb{F}_q[t_1, \dots,t_n] which vanishes on all points of $\mathbb{F}_q^n$ except one must have degree at least n(q-1). The Chevalley-Warning theorem, which is a statement on the zero set of a collection of polynomials over a finite field, has also found several applications in combinatorics. Alon, Friedland and Kalai used it to prove that every 4- regular graph plus an edge contains a 3-regular subgraph. Later, Bailey and Richter used the Chevalley-Warning theorem to give a new proof of the famous Erdős-Ginzburg- Ziv theorem from additive number theory. Recently, Clark, Forrow and Schmitt have shown that the Chevalley-Warning theorem and its combinatorial applications can be derived, and further generalized, using a result of Alon and Füredi from 1993. We will devote Chapter 9 to this Alon-Füredi Theorem, where we generalize the result and give a new simple proof. We also show how this result is linked to several other topics like coding theory, finite geometry and polynomial identity testing.

An important tool in the polynomial method involving zeros of polynomials is a result called Combinatorial Nullstellensatz. This powerful tool and its generalizations have been used extensively to solve several problems in additive number theory (see Chapter 9 of this for a survey) and more recently in some otherareas as well. In 2014, Clark revisited Alon’s Combinatorial Nullstellensatz and showed how its proof can be seen as a “restricted variable analogue” of Chevalley’s proof of the Chevalley-Warning Theorem. He further generalized this result to commutative rings (adding certain extra conditions) and made it clear how many of the ideas involved are related to the notion of grid reduction. Ball and Serra introduced a related result which they called Punctured Combinatorial Nullstellensatz. This result was proved using Alon’s Combinatorial Nullstellensatz, and it has several combinatorial applications of its own. We will give another proof of this result in Chapter 8 by directly using the notion of grid reduction, and then use this result to prove a new generalization of the Chevalley-Warning theorem which we call the Punctured Chevalley-Warning Theorem. In fact, this result generalizes Brink’s Restricted Variable Chevalley-Warning theorem.

In recent years, there has been a lot of interest in the polynomial method as a result of Dvir’s two-page proof of the finite field Kakeya problem which involved an easy polynomial argument, and the developments which followed. Many experts worked on the finite field Kakeya problem using different techniques involving algebraic geometry and Fourier analysis, but made only partial progress towards a solution to this problem. And thus it was a great surprise to the mathematical community that such an easy polynomial argument could resolve this famous open problem. Even more recently, the notorious cap set problem has been solved using the polynomial method by Ellenberg and Gijswijt. Ideas originating from Dvir’s work have lead to several important advancements in mathematics, including the big breakthrough in the famous Erdős distinct distances problem by Guth and Katz. It is interesting to note that Dvir’s polynomial technique is a bit different from the techniques we have mentioned so far in this introduction as it involved polynomial interpolation instead of constructing explicit polynomials. For more details on this, we recommend the surveys by Dvir and Tao, and the recent book by Guth. Another example where a combinatorial problem is solved using polynomial interpolation, combined with a geometric argument, is Segre’s classical theorem on ovals in finite projective planes. Interestingly, the so-called “lemma of tangents” of Segre was used in combination with the Jamison/Brouwer-Schrijver bound on affine blocking sets by Blokhuis and Korchmáros to solve the Kakeya problem in 2 dimensions. Segre’s result (and his lemma of tangents) has been generalized further to higher dimensional finite projective spaces by Ball. For more on polynomial method in finite geometry, see the survey by Ball.

Advertisements
Posted in Combinatorics, Incidence Geometry, Polynomial Method | Tagged , , , , | Leave a comment

On a famous pigeonhole problem

After a short break from blogging, which involved moving from Ghent to Berlin, dealing with German bureaucracy, and learning how to make simple websites (the easiest bit), I am now back. I am working as a postdoc at the Free University of Berlin right now and a part of my job is to teach a course (mainly taking care of the exercise classes) called Extremal Combinatorics with Tibor Szabó . While preparing a review sheet of exercises for this course, we discussed about which pigeonhole problem to include. In the actual sheet we ended up giving a simple one, but we did think about including the following famous problem:

Prove that if you pick any n + 1 numbers from 1, 2, \dots, 2n, there will be two distinct numbers a and b such that a divides b.

This used to be one of the favourite problems of Paul Erdős for young (mathematically inclined) kids. Quoting Proofs from THE BOOK, “As Erdős told us, he put this question to young Lajos Pośa during dinner, and when the meal was over, Lajos had the answer. It has remained Erdős’ famous initiation questions to mathematics”. Perhaps you should try it over your next dinner, before reading further.

So here is the standard pigeonhole argument for this. Every positive integer a can be written as a = 2^k(2m - 1), with k \geq 0 and m \geq 1 by considering the largest power of 2 in the factorisation of a. Now write each of the n + 1 numbers you have chosen in this form. Since there are precisely n odd integers in the set 1, \dots, 2n and hence precisely n possibilities for the 2m - 1 factor, by the pigeonhole principle we must have two integers a, b with a = 2^{k_1}(2m - 1) and b = 2^{k_2}(2m - 1), for some k_1 < k_2 and m \in \{1, \dots, n\}. Thus, a divides b.

Looking at the proof carefully, what we have really done is partition the set [2n] = \{1, \dots, 2n\} into n parts S_1, \dots, S_n, with S_i = \{2^k(2i - 1) : k \geq 0\} \cap [2n], such that in each S_i every number divides all the other numbers which are bigger. Then since we have chosen n + 1 elements from [2n] = S_1 \sqcup \dots \sqcup S_n, there must be an index i for which S_i contains two of these n + 1 elements.

Now, as a mathematician, there are two natural questions that one can ask:

(Q1) What is the largest possible size of a subset of [2n] which does not contain two elements with one dividing the other?

(Q2) Can we classify, or say something interesting about, all such largest possible subsets?

(Q1) is straightforward to answer, since we quickly see that the n-element subset \{n + 1, n + 2, \dots, 2n\} does not have any two distinct elements in it with one dividing the other. And since we have shown that any (n+1)-element subset will violate this property, n is the largest possible size.

(Q2) is what we will be really interested in.

This is such a natural question for a combinatorialist, but somehow I have been unable to find any reference for it (which Tibor found quite surprising as well). Now the first natural guess for an answer is that the example \{n + 1, n + 2, \dots, 2n\} is the unique n-element subset of [2n] with this “non-divisibility” property. It is natural because this is what happens in typical extremal combinatorics problems. But if you think about it for a while, you’ll be able to come up with the set \{n, n + 1, n + 2, \dots, 2n - 1\}, which is another such example. And then \{n - 1, n, n + 1, \dots, 2n - 3, 2n - 1\} is another one. We can keep doing this for a certain k = cn number of steps, where c is a constant (figure out what c is!). This shows that there are at least a linear number of extremal examples in this problem. Moreover, you can prove that any such extremal set must contain all the odd numbers from \{n + 1, n + 2, \dots, 2n\}. But are there any more such sets?

After some more thought, I was able to show that there are in fact exponentially many such extremal sets! More precisely, there exists a constant c > 1 such that there are at least c^n n-element subsets of [2n] in which there are no two elements with one dividing the other. I will leave the proof of this as an exercise, since it did not take me too long to come up with it and in fact, one of the students in the exercise classes that I teach was able to come up with the same proof as mine pretty quickly.

Now the questions that I want to ask are the following:

What is the best possible value of the base c? In other words, asymptotically how many such extremal subsets can we find? Is there a “substantially” better upper bound on the number of such sets than \binom{3n/2}{n/2} \sim 2^{1.38 n}?

If you have an answer, or some ideas, then please let me know in the comments.

Edit 06/11/2017: I computed the number of such extremal subsets for small values of n, after which a quick search on The On-Line Encyclopedia of Integer Sequences revealed that people have computed and studied this number.  In particular, Robert Israel mentions the same lower bound that I obtained.

 

 

Posted in Combinatorics, Extremal Combinatorics | Tagged , , , , | 5 Comments

What I have learned in finite geometry

On September 2nd, 2014 I wrote a blog post titled learning finite geometry, in which I described how much I have learned in my first year of PhD and more importantly, the topics that I wish to learn while I am in Ghent. Since I’ll be leaving Ghent in a few days, I feel like this is the right time reflect on that old post. I am quite happy to see that beyond just learning those topics, I have also been able to do some research on them. Here are the topics that I described in my previous blog post:

1. Blocking sets
Two of my papers have results on blocking sets. In the first one, I used the Alon-Furedi theorem to prove old and new results on partial covers and blocking sets with respect to hyperplanes in finite Desarguesian affine/projective spaces. I have given a new common framework for treating some of the problems on blocking sets in an easy way using the polynomial method. See section 6 of my paper for the details.

In my second paper, I have proved a generalisation of a classical result in finite geometry from the 1970s due to Aiden A. Bruen and Jeff Thas. Moreover, I have done so with a new method involving the expander mixing lemma which has lead to a unified (and simple) approach to problems related to blocking sets, Nikodym sets and tangency sets. This method is quite interesting in its own right as it has also lead to some advancements in the cage problem.

2. Unitals
These objects appear in my second paper on blocking sets, as they were used by Sam to give a construction of large minimal multiple blocking sets in finite projective planes. In fact, as Sam has described in his blog post, an open problem on unitals was one of my motivations to look at these blocking sets. Sadly, we haven’t been able to solve that open problem yet.

3. Polar Spaces
After the end of my first year, I had seen polar spaces appear in almost every other research paper and talk in finite geometry. Even though I had read and understood the definitions of these objects in my first year, I wasn’t really comfortable with them. I am not sure when exactly that changed, but it was certainly quite gradual. In my paper with John and Gordon, on regular induced subgraphs of generalized polygons, I have used some of the basic theory of polar spaces to give new constructions of small k-regular graphs of girth g with g = 8, 12. Before that I also refereed a paper which helped me revisit some of the basics of the axiomatic theory of polar spaces. Overall, I can say that I have made pretty good progress towards understanding polar spaces. I now wish that more mathematicians would learn the basic theory of these beautiful geometrical objects, especially because people sometimes obtain results on specific classes of finite polar spaces without realising it (see this for example). The new book “Finite Geometry and Combinatorial Applications” by Simeon Ball can be a useful resource for anyone interested in doing so.

Besides these topics, I have also learned about several combinatorial problems in which finite geometry plays an important part. For example, the cage problem, forbidden subgraphs, and ramsey numbers. During my postdoc years, I will work on finding more such combinatorial applications of finite geometry, and using various tools from combinatorics to solve problems in finite geometry.

Posted in Combinatorics, Finite Geometry, Incidence Geometry, Research Diary | Tagged , , , , , , | Leave a comment

The cage problem and generalized polygons (part 1)

This post is a continuation of my previous post on the cage problem. Just to recall the main problem, for any given integers k \geq 2 and g \geq 3, we want to find the least number of vertices in a simple undirected graph which is k-regular and has girth g. The least number is denoted by c(k, g) and the (k, g)-graphs with c(k, g) vertices are called cages. As we saw before, besides the generalized polygons of order q, for some prime power q, there are no know infinite families of cages (for a list of all known cages, see the survey by Excoo and Jajcay. ). And by the result of Feit and Higman on generalized polygons, we see that these infinite families have g \in \{6, 8, 12\}. It turns out that we know a lot more about c(k, g) for g \in \{6, 8, 12\} than the general case, even when there is no known generalized polygon of order k - 1, i.e., when k - 1 is not a prime power.

Let’s start with an example. For every prime power q, we know that c(q + 1, 6) = 2(q^2 + q + 1) by looking at the incidence graph of a finite projective plane (i.e., a generalized 3-gon) \pi of order q. Now pick a point X in \pi and a line \ell through X. Then observe that through each point Y \neq X, there are exactly q lines which do not contain X: all the lines through Y except the line XY. Dually, every line m \neq \ell contains exactly q points which do not lie on \ell: all points on m except the intersection point of \ell and m. What this shows is that if we take the subgraph of the incidence graph of \pi induced on the q^2 points not contained in \ell and the q^2 lines not containing X, then it is a q-regular graph. Moreover, this graph has girth 6, which leave as an exercise to the reader. So, we have just constructed a q-regular graph of girth 6 with 2q^2 vertices, proving that \displaystyle c(q, 6) \leq 2q^2 for all prime power q.

In fact, we can do slightly better if we take X \not\in \ell. We then take all the points distinct from X which are not on \ell, and all the lines distinct from \ell which do not contain X. This gives us a q-regular subgraph on 2(q^2 - 1) vertices, proving c(q, 6) \leq 2(q^2 - 1) (not a big improvement, I know). But is this the best that we can do by pursuing this idea of constructing q-regular induced subgraphs?

Interestingly, there is something much better that can be done, if q is a square. We can take the subgraph induced on the points and lines of \pi which are not contained in a Baer subplane of \pi. In the Desarguesian plane \mathrm{PG}(2,q), we can get a Baer subplane by restricting the co-ordinates of the points and lines to the subfield \mathbb{F}_{\sqrt{q}} (similarly the real projective plane \mathrm{PG}(2, \mathbb{R}) is a Baer subplane of the complex projective plane \mathrm{PG}(2, \mathbb{C})). While every subfield of \mathbb{F}_q gives rise to a subplane of \mathrm{PG}(2,q), the Baer subplane in particular has the following nice properties:

  • through every point outside the subplane there is a unique line of the subplane;
  • every line outside the subplane contains a unique point of the subplane;

In other words, the induced subgraph that we get on the points and lines not contained in the Baer subplane is q-regular. This construction gives us c(q, 6) \leq 2(q^2 + q + 1 - q - \sqrt{q} - 1) = 2(q^2 - \sqrt{q}), which is much better than the previous bound of 2(q^2 - 1). But, this construction only works when q is a square.

So now the natural question arises (as it always should!), is this the best that we can do? Interestingly, now the answer is yes. We have actually reached a theoretical lower bound on the size of a q-regular induced subgraph in a projective plane of order q. This is a consequence of the following result that tells us how small a k-regular induced subgraph of a d-regular bipartite graph be.

Theorem 1. Let G = (L, R, E) be a d-regular bipartite graph and let \lambda be its second largest eigenvalue. Let H be a k-regular induced subgraph of G. Then |V(H)| \geq (k - \lambda)|V(G)|/(d + \lambda).

Theorem 1 can be proved easily using the expander mixing lemma, which I discussed in a previous post. It is well known, and easy to show, that the second largest eigenvalue of the incidence graph of a generalized n-gon of order q is \sqrt{q}, \sqrt{2q} and \sqrt{3q} for n = 3, 4 and 6, respectively. The number of vertices in the incidence graphs of a generalized n-gon is q^2 + q + 1, (q + 1)(q^2 + 1) and (q + 1)(q^4 + q^2 + 1) for n = 3, 4 and 6 respectively. If we now substitute these values in Theorem 1, and note the factorisations q^2 + q + 1 = (q + \sqrt{q} + 1)(q - \sqrt{q} + 1), q^2 + 1 = (q + \sqrt{2q} + 1)(q - \sqrt{2q} + 1) and q^4 + q^2 + 1 = (q^2 + q + 1)(q + \sqrt{3q} + 1)(q - \sqrt{3q} + 1) (thanks Sam!), we get the following result.

Theorem 2. Let G be the incidence graph of a generalized n-gon of order q, and let H be a (q + 1 - t)-regular induced subgraph, for some t \geq 1. Then

\displaystyle|V(G)| - |V(H)| \geq \begin{cases} 2t(q + \sqrt{q} + 1), & \text{if } n = 3;\\ 2t(q + 1)(q + \sqrt{2q} + 1), & \text{if } n = 4; \\ 2t(q+1)(q^2 + q + 1)(q + \sqrt{3q} + 1), & \text{if } n = 6. \end{cases}

In particular, for n = 3 and t = 1, we get 2(q^2 + q + 1) - |V(H)| \geq 2(q + \sqrt{q} + 1), i.e., V(H) \leq 2(q^2 - \sqrt{q}). Therefore, the construction using the Baer subplane is the best possible. In fact, for n = 3 and arbitrary t, we have a construction using t disjoint Baer subplanes (see Construction 3.7 here) which is sharp according to this new bound. So, the problem of looking at regular induced subgraphs is settled for projective planes. For generalized quadrangles and hexagons though, there is a lot more to be said. In collaboration with John Bamberg and Gordon Royle, I have obtained some new finite geometrical constructions which improve the bounds on c(q, 8) and c(q, 12). We will discuss that in the next post.

Posted in Combinatorics, Finite Geometry, Incidence Geometry, Spectral Graph Theory, Uncategorized | Tagged , , , , | Leave a comment

The coefficient formula and Chevalley-Warning

This post is about a certain result on coefficients of a multivariate polynomial obtained by Schauz, Lason and Karasev-Petrov, which generalises Alon’s combinatorial nullstellensatz (or to be more precise, Theorem 1.2 in Alon’s paper). This sharpening of Alon’s result has seen some very interesting applications, for example a short proof of dyson conjecture and its q-analog. Now there is a new application by Pete Clark who has used it to obtain a simultaneous generalization of Chevalley-Warning and Morlaye’s theorem, building up on the work of Baoulina.  We will see how this result is proved.

If f is a single variable polynomial of degree d over a field K, then the values of f over any arbitrary set S of d + 1 elements from K completely determines f. This is basically Lagrange’s polynomial interpolation. One way of seeing it is to define the polynomials \delta_x(t) = \frac{\varphi(t)}{\varphi'(t)(t - x)} for each x \in S where \varphi(t) = \prod_{s \in S}(t - s) and note that \delta_x(s) = 1 if x = s and 0 otherwise. Then for each s \in S we have f(s) = \sum_{x \in S} f(x) \delta_x(s). And since no two degree d polynomials can agree in more than d points, we deduces that the polynomial f must be equal to the polynomial \sum_{x \in S} f(x) \delta_x = \sum_{x \in S} f(x) \prod_{s \in S \setminus \{x\}}\frac{t - s}{x - s}. The situation becomes quite different when we look at polynomials in n variables, but in fact we can still say something quite interesting using the same ideas.

Theorem 1. (Coefficient Formula) Let f \in K[t_1, \dots, t_n] be a polynomial of degree at most a_1 + \cdots + a_n for some positive integers a_i. Let A_1, \dots, A_n be finite subsets of K with |A_i| = a_i + 1. Then the coefficient of t_1^{a_1}t_2^{a_2} \cdots t_n^{a_n} in f is equal to

 \displaystyle \sum_{(x_1, \dots, x_n) \in A_1 \times \cdots \times A_n} \frac{f(x_1, \dots, x_n)}{\phi_1'(x_i)\cdots\phi_n'(x_n)}

where \varphi_i(t_i) = \prod_{x \in A_i}(t_i - x).

Unlike the single variable case, the Coefficient formula does not uniquely determine the full polynomial but just some coefficients of the polynomial. This looks quite weak, but surprisingly it has some really interesting consequences. For a proof of Theorem 1 look at these notes (Theorem 13) or any of the original papers.

Let’s first see how this a generalization of Alon’s combinatorial nullstellensatz.

Theorem 2. (Combinatorial Nullstellensatz) Let f \in K[t_1, \dots, t_n] and suppose that the coefficient of the monomial \prod_{i = 1}^n t_i^{d_i} in f is non-zero where d_1, \dots, d_n are some positive satisfying \deg f = d_1 + \cdots + d_n. Then for any finite subsets A_1, \dots, A_n of K satisfying |A_i| > d_i for all i, there exists (a_1, \dots, a_n) \in A_1 \times \cdots \times A_n such that f(a_1, \dots, a_n) \neq 0.

Proof: We have \deg f \leq \sum (|A_i| - 1). Then by Theorem 1, we get

\displaystyle \sum_{(x_1, \dots, x_n) \in A_1 \times \cdots \times A_n} \frac{f(x_1, \dots, x_n)}{\varphi_1'(x_1) \cdots \varphi_n'(x_n)} \neq 0,

which implies that there exists an (a_1, \dots, a_n) \in A_1 \times \cdots \times A_n for which f(a_1, \dots, a_n) \neq 0. \blacksquare

Therefore, Theorem 2 is a direct consequence of Theorem 1. Let’s now see how Theorem 1 can sometimes give more general results than Theorem 2.

One of the first applications of combinatorial nullstellensatz that Alon gave in his paper was to prove that the classical Chevalley-Warning theorem follows directly from his result. Actually, he only proved the weaker form of Chevalley-Warning (also known as Chevalley’s theorem), which is as follows: let f_1, \dots, f_r \in \mathbb{F}_q[t_1, \dots, t_n] such that \sum \deg f_j < n, then for Z = \{x \in \mathbb{F}_q^n : f_1(x) = \cdots = f_r(x) = 0\} we have |Z| \neq 1. The stronger form says that the characteristic p of the finite field \mathbb{F}_q divides |Z|. This can be proved using Theorem 1 as follows.

Define f := \prod_{j = 1}^r (1 - f_i^{q - 1}). Then \deg f = (q - 1) \sum \deg f_j, and f(x) = 1 for all x \in Z and 0 otherwise. Since \deg f < (q - 1) + (q - 1) + \cdots + (q - 1), the coefficient of t_1^{q-1} \cdots t_n^{q - 1} in f is equal to 0, and we can apply Theorem 1 to get

\displaystyle 0 = \sum_{(x_1, \dots, x_n) \in \mathbb{F}_q^n} \frac{f(x_1, \dots, x_n)}{\varphi'_1(x_1)\cdots\varphi_n'(x_n)} = \sum_{(x_1, \dots, x_n) \in Z} \frac{1}{\varphi'_1(x_1)\cdots\varphi_n'(x_n)},

where \phi_i(t_i) = \prod_{\lambda \in \mathbb{F}_q} (t_i - \lambda). We will now use Lemma 3 below, which is a nice result on finite fields that will be useful in another context as well. In particular that result will show that \prod_{\mu \in \mathbb{F}_q, \mu \neq \lambda} (\lambda - \mu) = -1 for every \lambda \in \mathbb{F}_q. Therefore, our equation simplifies to 0 = \sum_{x \in Z} (-1)^n = |Z|(-1)^n. This means that the characteristic p of the field \mathbb{F}_q must divide |Z|, which is the stronger Chevalley-Warning theorem. \blacksquare

Lemma 3. Let d be a divisor of q - 1 and let X = \{x^d : x \in \mathbb{F}_q\}. Define \phi(t) = \prod_{x \in X} (t - x). Then:

  1. \phi'(0) = -1.
  2. For all x \in X, we have \phi'(x) = -1/d.

Proof. Note that \phi'(t) = \sum_{x \in X} \prod_{y \in X \setminus \{x\}} (t - y).

  1. We have \phi'(0) = \prod_{x \in X \setminus \{0\}} (-x) = (-1)^{(q-1)/d} \prod_{x \in X \setminus \{0\}} x. Let \theta be a primitive element of \mathbb{F}_q, then we have X = \{0\} \cup \{\theta^{di} : 1 \leq i \leq (q - 1)/d\}. Therefore,
    \displaystyle \prod_{x \in X \setminus \{0\}} x = \theta^{\frac{(q - 1)}{2}((q - 1)/d + 1)}= (-1)(-1)^{(q - 1)/d}
    where the las equality follows from the fact that \theta^{(q-1)/2} = -1.
  2. Let x \in X \setminus \{0\}. Then
    \displaystyle \phi'(x) = \prod_{y \in X \setminus \{x\}} (x - y)  = x \prod_{y \in X \setminus \{0, x\}} (x - y) = x \cdot x^{(q - 1)/d - 1} \prod_{y \in X \setminus \{0, x\}} (1 - y/x) = 1 \cdot \prod_{\lambda \in X \setminus \{0, 1\}} (1 - \lambda) = \phi'(1).
    Since the elements of X \setminus \{0\} are all the \frac{q - 1}{d}th roots of unity, we have \prod_{\lambda \in X \setminus \{0,1\}} (t - \lambda) = (t^{(q - 1)/d} - 1)/(t - 1) = 1 + t + t^2 + \cdots + t^{(q - 1)/d - 1}. Therefore, \phi'(1) = (q - 1)/d = -1/d. \blacksquare.

We now have all the ingredients for the new result of Clark, which is a generalization of Chevalley-Warning theorem obtained by restricting the variables to power residues. More precisely, we have the following:

Theorem 3. (Clark 2017) For 1 \leq i \leq n - 1 let m_i be a positive integer and define d_i = \gcd(m_i, q - 1). Let f_1, \dots, f_r \in \mathbb{F}_q[t_1, \dots t_n] be such that

\displaystyle \sum_{j = 1}^r \deg f_j < \sum_{i = 1}^n \frac{1}{d_i}.

Then the characteristic p of \mathbb{F}_q divides the cardinality of the set Z = \{(x_1, \dots, x_n) \in \mathbb{F}_q^n : f_1(x_1^{m_1}, \dots, x_n^{m_n}) = \cdots = f_r(x_1^{m_1}, \dots, x_n^{m_n}) = 0\}.

Proof. Apply all the tools so far carefully, or see Pete’s paper.

When all m_i‘s are equal to 1, Theorem 3 is just the Chevalley-Warning theorem. When r = 1 and \deg f_1 = 1, then this is a result due to Morlaye. Morlaye’s result has been generalized by Wan to prove that if \sum 1/d_i > b \geq 1 = \deg f_1, then q^b divides |Z|.

Question. Is there such a generalization of Theorem 3, or some other special case of it?

 

Posted in Number Theory, Polynomial Method | Tagged , , , , , , | 2 Comments

The Cage Problem

I recently finished my research visit to UWA where I worked with John Bamberg and Gordon Royle on some finite geometrical problems related to cages. So this seems like the right time for me to write a blog post about these graphs.

A (k,g) graph is a simple undirected graph  which is k-regular and has girth g, or in other words, every vertex in the graph is adjacent to exactly k other vertices and the length of the shortest cycle in the graph is g. For example, the following is a (3, 5) graph, which is the well-known Petersen graph.

10edb-petersen-svg

Say G is a (k, 5) graph. Pick a vertex v of G. Then there are k vertices of G adjacent to v. None of these k vertices are adjacent among each other since that would give us a triangle in G, which contradicts the fact that the girth of G is five. Each of these k vertices is adjacent to k -1 more vertices besides v, all of which must lie at distance 2 from v. Moreover, these k(k-1) vertices are distinct since otherwise we will get a cycle of length 4 in G. Therefore, we see that G has at least 1 + k + k(k-1) vertices. Note that for k = 3 this number is equal to 10, and hence the Petersen graph above is the smallest (3,5) graph.

The argument above generalises to show that for odd g, the number of vertices in a (k, g) graph is at least 1 + k + k(k-1) + \cdots + k(k-1)^{(g-3)/2}. When g is even we can count the number of vertices at distance at most (g-2)/2 from a fixed edge, which shows that the number of vertices is at least 2(1 + (k-1) + \cdots + (k-1)^{(g-2)/2}). These lower bounds on the number of vertices in a (k,g) graph are collectively known as the Moore bound and the (k, g) graphs which have these many vertices are known as Moore graphsThe Petersen graph above is an example of a Moore graph. Interestingly, there are very few Moore graphs!

Using spectral methods, it has been shown that the Moore graphs can only exist in the following cases: (a) k = 2 and g \geq 3 (cycles), (b) g = 3 and k \geq 2 (complete graphs), (c) g = 4 and k \geq 2 (complete bipartite graphs), (d) g = 5 and k \in \{2, 3, 7, 57\}, (e) g \in \{6, 8, 12\} and there exists a generalized g-gon of order k - 1. The (3, 5) Moore graph is the Petersen graph, the (7,5) Moore graph is the Hoffman-Singleton graph and its a famous open problem in mathematics whether a (57, 5) Moore graph exists or not. Generalized n-gons are certain point line geometries that were defined by Tits in his famous paper on trialities, and they are precisely the rank 2 buildings. Their incidence graph is biregular, has diameter n, and girth 2n. Those generalized n-gons whose incidence graph is regular with degree k can only exist for n \in \{6, 8, 12\} and in each of these cases we only have constructions where k - 1 is a prime power! We are nowhere near proving that k - 1 has to be a prime power. For example, whether a projective plane (which equivalent to a generalized 3-gon) of order 12 exists or not is still a big open problem.

Since there are very special values of k and g for which a (k,g) Moore graph exists, it is natural to consider the following problem:

Find the smallest number of vertices c(k,g) in a (k,g) graph.

The (k,g) graphs which have exactly c(k, g) vertices are known as cages. It was shown by Erdős and Sachs (see the Appendix in the survey on cages *) that cages exist for every value of k \geq 2 and g \geq 3. But besides the Moore graphs, explicit examples of cages, or equivalently the exact value of c(k,g) is only known for a few values of k and g. See the database of Brouwer for a full list and description of the known cages.

Therefore, a natural problem that mathematicians have worked on is to construct small (k, g) graphs and thus improve the upper bounds on (k, g). The bound that Erdős and Sachs proved is c(k, g) \leq 4 \sum_{i = 1}^{g - 2} (k -1)^i which was improved later by Sauer to c(k,g) \leq 2(k-2)^{g-2} for g odd and c(k,g) \leq 4(k-1)^{g-3} for  g even. These upper bounds are roughly square of the Moore bound. This square was improved to 3/2 power by Lazebnik, Ustimenko and Woldar who proved that if q is the smallest odd prime power bigger than k, then c(k, g) \leq 2kq^{3g/4 - a} where a = 4, 11/4, 7/2, 13/4 for g \equiv 0, 1, 2, 3 \pmod{4}. Since we can always find an odd prime between k and 2k, this bound is roughly of the power 3/2 of the lower bound.

For specific values of g, the known upper bounds are in fact much better than these general bounds. I will talk about how these bounds are obtained for g \in \{6, 8, 12\} by looking at certain subgraphs of the known Moore graphs in a later post where I will also discuss our new results in this direction.

Further Reading

[1]  Dynamic Cage Survey by Geoffrey Excoo and Robert Jajcay.

[2] The cage problem by Michael Giudici.

[3] Balaban 10-cage | Visual Insight by John Baez.

 

* A simpler proof using Cayley graphs was later given by Biggs. In both of these proofs we need the fact that for all k \geq 3 and 3 \leq g_1 < g_2, we have c(k, g_1) < c(k, g_2). The only place where I have found an explicit proof of this is in the paper of Fu, Huang and Rodger.

Posted in Combinatorics, Finite Geometry | Tagged , , , , , | 2 Comments

Expander Mixing Lemma in Finite Geometry

In this post I will discuss some nice applications of the expander mixing lemma in finite incidence geometry, including a new result that I have obtained recently.

In many of the applications of the lemma in finite geometry, the graph is bipartite, and therefore let’s start by recalling the bipartite version of the expander mixing lemma that I described in my last post.

Lemma 1. Let G = (L, R, E) be a semiregular bipartite graph with degrees d_L and d_R. Let S \subseteq L and T \subseteq R such that |S| = \alpha|L| and |T| = \beta |R|. Define e(S, T) = |\{(x, y) \in S \times T \mid \{x, y\} \in E\}|. Then we have

|\frac{e(S,T)}{e(G)} - \alpha \beta| \leq \frac{\lambda_2}{\lambda_1} \sqrt{\alpha \beta(1 - \alpha)(1 - \beta)},

where \lambda_1 = \sqrt{d_Ld_R} is the largest eigenvalue of G, \lambda_2 is the second largest eigenvalue of G in absolute value, and e(G) is the total number of edges in G.

There are interesting bipartite graphs related to finite geometries, block designs and other combinatorial structures, for which we know the second largest eigenvalue of the graph exactly. For example, the incidence graph (a.k.a. Levi graph) of a finite projective plane of order n has eigenvalues n + 1, \sqrt{n}, -\sqrt{n}, -n-1 (the eigenvalues of a bipartite graph are always symmetric around the origin). And more generally, the eigenvalues of the incidence graph of a 2(v, k, \lambda) design are \pm \sqrt{rk}, \pm \sqrt{r - \lambda}, 0. Therefore, applying expander mixing lemma to these graphs can potentially give some nice results in finite geometry. Let’s start with one of the classical results in the area of finite geometry and see how it can be proved using Lemma 1.

A blocking set in a finite projective plane (or in general, any hypergraph) is a set B of points with the property that for every line \ell of the plane we have |\ell \cap B| \geq 1. One of the central problems in the area of finite geometry has been to understand the possible sizes of a minimal blocking set, where a blocking set B is minimal if no proper subset of B is also a blocking set. If we do not assume minimality, then this problem becomes trivial as you can obtain a blocking sets of any size by adding some points to a given blocking set. The simplest, and the smallest!, example of a blocking set is a line of the projective plane since every two lines intersect each other. This gives us a blocking set of size n + 1, which we a trivial blocking set. For a non-trivial minimal blocking set B, Bruen and Thas proved the following result, which is one of the main starting points for a systematic study of blocking sets:

n + \sqrt{n} + 1 \leq |B| \leq n \sqrt{n} + 1.

Here is a new proof of the upper bound which uses Lemma 1. For each point x of B there must exist a line \ell_x such that \ell_x \cap B = \{x\} since otherwise B \setminus \{x\} will also form a blocking set, contradicting the minimality of B. We can choose a single such line for each point of B to get a set \mathcal{L} of lines in the projective plane with the property that (a) |\mathcal{L}| = |B| and (b) the number of edges between the sets B and \mathcal{L} in the incidence graph is exactly |\mathcal{L}|. The number of points/lines in a projective plane of order n is n^2 + n + 1. By applying Lemma 1, taking S = B, T = \mathcal{L} and defining b := |B|, we get the following:

|b - (n + 1)b^2/(n^2 + n + 1)| \leq \sqrt{n} \sqrt{b^2(1 - b/(n^2 + n + 1))^2}.

We must have b \geq n + 1 since B is a blocking set (prove it!) and therefore b(n+1) > n^2 + n + 1, which helps us remove the mod sign in the inequality. We get

(n + 1)b/(n^2 + n + 1) - 1 \leq \sqrt{n}(1 - b/(n^2 + n + 1)),

which simplifies to

b \leq (\sqrt{n} + 1)(n^2 + n + 1)/(n + \sqrt{n} + 1).

Since n^2 + n + 1 = (n + 1 - \sqrt{n})(n + 1 + \sqrt{n}), we get

b \leq (\sqrt{n} + 1)(n - \sqrt{n} + 1) = n \sqrt{n} + 1. \Box

Question 1. Can the lower bound on non-trivial minimal blocking sets be proved using eigenvalue methods as well?

The proof above is quite flexible as it can be easily adapted to similar situations, sometimes giving us new results. One such result is about minimal multiple blocking sets that I  obtained while exploring the power of this method.

A t-fold minimal blocking in a projective plane of order n is a set B of points with the property that (a) for each line \ell, we have |\ell \cap B| \geq t, and (b) through each point x \in B, there exists a line \ell_x with the property that |\ell_x \cap B| = t. We will prove that

|B| \leq \frac{1}{2} n\sqrt{4tn - (3t + 1)(t - 1)} + \frac{1}{2} (t - 1)n + t.

Again, we define a set of lines \mathcal{L} by taking a single line \ell_x through each x \in B. But this time we have t|\mathcal{L}| \geq |B|. By getting rid of a few lines we can assume that |\mathcal{L}| = |B|/t (technically it should be |\mathcal{L}| = \lceil |B|/t \rceil, but it can be checked later that this won’t affect the proof). The number of incidences between B and \mathcal{L} is still |B| since each line is incident with exactly t points. Therefore, by applying Lemma 1 again we get

\left\lvert b - \frac{(n+1)b^2}{t(n^2 + n + 1)} \right\rvert \leq \sqrt{n\frac{b^2}{t}\left(1 - \frac{b}{(n^2 + n+ 1)}\right)\left(1 - \frac{b}{t(n^2 + n + 1)}\right)}.

This can be simplified to the following quadratic inequality:

b^2 - ((t - 1)n + 2t)b - t(n - t)(n^2 + n + 1) \leq 0.

This implies that b must lie between the two roots of the quadratic equation x^2 - ((t - 1)n + 2t)x - t(n - t)(n^2 + n + 1) = 0, which gives us the required bound. \Box

For more applications of this proof method, see my preprint “Minimal multiple blocking sets” on arXiv.

Another interesting result in finite geometry that can be obtained easily via Lemma 1 is the following Theorem of Stefaan De Winter, Jeroen Schillewaert and Jacques Verstraete on incidence free subsets. For an incidence structure \Pi = (P, L, I), let \alpha(\Pi) be the largest value of |X||Y| where X \subseteq P and Y \subseteq L such that there are no edges between X and Y in the incidence graph of \Pi. Then for P equal to the set of points in the finite projective space \mathrm{PG}(n, q) and L equal to the set of k-dimensional spaces in \mathrm{PG}(n, q), we have

\alpha(\Pi) \approx q^{(k + 2)(n - k)}.

This follows directly from Lemma 1 by observing that this incidence structure \Pi formed by taking points and k-spaces of \mathrm{PG}(n,q) is in fact a 2({n + 1 \brack 1}_q , {k + 1 \brack 1}_q, {n - 1 \brack k - 1}_q) design with r = {n \brack k}_q.

Just last week, a new application of the expander mixing lemma to a graph theoretical problem related to finite geometry has appeared on arXiv. Jared Loucks and Craig Timmons have proved that the largest triangle free induced subgraph of the polarity graph of a projective plane of order n, with respect to any polarity \theta, has at most (n^2 + n + 1)/2 + \sqrt{n}(n^2 + n + 1)/(n + 1) vertices. The polarity graph is defined by taking the points as vertices and making two points x and y adjacent if and only if x \in \theta(y). These graphs were introduced by Erdős and Renyi for the special case of orthogonal polarity, and independently by W. G. Brown. They have since been used in many problems in extremal graph theory.

I am sure that there are plenty of interesting applications of the expander mixing lemma in finite geometry and extremal graph theory waiting to be discovered. I will soon write about another new result in this direction which I proved a couple of weeks back.

Posted in Combinatorics, Finite Geometry, Incidence Geometry, Spectral Graph Theory | Tagged , , , , | 2 Comments