Adv Poly Method

This unit used to be only about combinatorial nullstellensatz; it was expanded in January 2024 to be broader in scope.

About Adv Poly Method

Adv Poly Method was a relatively short yet very fun unit about the advanced, extremely over-powered tool known as combinatorial nullstellensatz, later expanded to include uses of related methods. It is an easier unit overall for a Z unit, but it is still recommended to only do this unit after having significant grounding in more basic combinatorics techniques, as they are far more important than this (think about learning moving points before similar triangles, or Eisenstein's criterion before modular arithmetic). On the other hand, the problems that can be solved by Combo Null are rarely ever solvable using other techniques (similar to how Hall problems are "hard to crack" without Hall's Marriage Theorem), making it worthwhile to learn for those more advanced at combinatorics (looking at you, combo mains!).

With this in mind, the problem set of Combo Null is quite focused on the single concept of combinatorial nullstellensatz, so don't expect much diversity or variation out of it (quite similar to the gen func or ineq func units in that sense). The manner of applying combo null is somewhat of an art form, so you will never be bored, of course, but the fact that you know combo null will need to be applied makes the problems somewhat easier than you might expect.

All in all, it is a fantastic unit to do for people who are looking to learn an interesting trick, and possibly gain a few points on an olympiad :eyes:

Combo Null Theorem

Here is the statement of combinatorial nullstellensatz:

Let $f(x_1,\ldots ,x_n)$ be a polynomial over a field $\mathbb{F}$. Suppose that the coefficient of the monomial $x_1^{k_1}\cdots x_n^{k_n}$ in $f$ is nonzero and $k_1+\cdots +k_n$ is the total degree of $f$. If $A_1,\ldots ,A_n$ are finite subsets of $\mathbb{F}$ with $|A_i|>k_i$ for $i=1,\ldots ,n$, then there are $a_1\in A_1,\ldots ,a_n\in A_n$ such that $f(a_1,\ldots ,a_n)\neq0$.

To learn more about this, you can read this wikipedia page, or read this paper or this paper. Alternatively, you can do this unit! :D

Notable Problems

Note: "Alon" refers to "Noga Alon", the creator of combinatorial nullstellensatz, not "Alon Ragoler", the creator of this article :P

Some notable problems in this unit include:

• Alon's hyperbase problem - simple application of combo null
• Problem from Alon - Representative of the mid-range of the problem set
• ISL 2003 N8 - Representative of the harder range of the problem set
• Problem from Alon and Knuth - Beautiful application of combo null