Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
By Chevalley-Warning theorem, $N_p \equiv 0 \pmod{p}$, and not what you wrote. In particular, if there is a solution, then there are at least $p$ of them. When $n > \sum d_j$, then there is also a nicer bound called Warning's second theorem which says that if there is a common solution, then there are at least $p^{n - \sum d_i}$ common solutions: arxiv.org/abs/1404.7793.
One can skip Alon's combinatorial nullstellensatz here and directly show this as follows: (a) every polynomial $f$ corresponds to a unique reduced polynomial $\tilde{f}$ (degree of the $i$-th variable is at most $|S_i| - 1$) such that $f$ and $\tilde{f}$ take the same values on $S_1 \times \dots \times S_n$, (b) degree of $f$ is greater than or equal to the degree of $\tilde{f}$. See anuragbishnoi.files.wordpress.com/2016/04/grid_reduction.pdf (Theorem 9) where all the details are worked out in much more generality.
Is this inspired from the recent solution of cap-set problem? Even though Gijswijt doesn't make it that explicit, the following is used in his proof, homepage.tudelft.nl/64a8q/progressions.pdf: "Every $k$-dimensional subspace of $F^n$ has a vector in it that has at least $k$ non-zero coordinates", and I found it not so obvious when I first read it. It's basically the last step where he shows that $\dim V = |A'| \leq 2 \dim L_{n, \frac{1}{3}(p-1)n}$.
This exact definition is also used in the theory of near polygons: en.wikipedia.org/wiki/Near_polygon. One of the most basic/important structural result for near polygons is about existence of "quads", which are basically convex subsets isomorphic to generalized quadrangles: en.wikipedia.org/wiki/Generalized_quadrangle, roughly under the condition that every two points at distance 2 from each other have more than one common neighbours.
Such a collection of vectors corresponds to MDS codes. An easy to prove bound is that there are at most $q + m - 1$ such vectors, where $q = p^k$. Google "MDS codes", and "MDS conjecture" (recently solved in the prime case by Simeon Ball).
@PeterMueller: And I suppose you can get that upper bound as follows: Let $f$ be an affine transformation given by $f(x) = Ax + b$, and let $d$ be the order of $A$. Then $f^n(x) = A^nx + (A^{n-1} + \dots + A + I)b$ for all $n$, which gives us $f^{pd}(x) = A^{pd}x + p(A^{d-1} + \dots + A + 1)b = x$. Though I am still curious about the sharpness of this bound. Any ideas?
Thanks. I was just looking at $AGL(2, q)$ for small $q$'s and it seemed to work there, but I couldn't find a general argument. For $q = 3$ I used the Cayley-Hamilton theorem to show that no element has order $9$ (which is related to cyclic Steiner Triple Systems), but it probably doesn't work in general.
I should add that by a blocking set in a finite projective plane, we mean a set of points which intersects every line but does not contain a line, as otherwise the smallest blocking sets are lines of the plane.
Ah, I see. I'll have to think about that. It could be that the asymptotics are the same here and the conjecture for the prime case is wrong. Anyway, if you look at blocking sets in finite projective planes, then an old result of Bruen states that it has size at least $q + \sqrt{q} + 1$ (even when the plane is non-Desarguesian), with equality iff the blocking set is a Baer subplane (which only exist for $q$ square). While for $PG(2,p)$, $p$ prime, Blokhuis proved that a blocking set has size at least $3(p+1)/2$ (the bound is sharp). This could be a possible example in a certain sense.
