Skip to main content
2 of 3
added def of dependency graph
domotorp
  • 18.9k
  • 3
  • 57
  • 127

Vanishing product of polynomials over finite fields

$(x_1-x_2-x_3+x_4)(x_2-x_4-x_3+x_1)(x_3-x_1)(x_4-x_2)\equiv 0$ over $\mathbb F_3$.

Take polynomials $p_1,\dots,p_n$ over variables $x_1,\dots,x_n$ such that $p_i$ does not depend on $x_i$ and $\Pi_{i=1}^n (x_i+p_i) \equiv 0$ over $\mathbb F_q$.
It is easy to see that one can take $n=q$ and $p_i=i+\sum_{j\ne i} x_j$ to satisfy this equation.
If each $p_i$ can depend on only a bounded number of variables, then it follows from the Local Lemma that this is not possible.
It is not that hard to show that for $n=2^{q-1}$ there are polynomials such that each $p_i$ depends on only one $x_j$ with $j<i$; see the example in the first line for $q=3$.

In general, have such polynomials been studied in number theory?

My motivation comes from that this is an equivalent reformulation of the Hat Guessing Number of graphs.
To decide whether such polynimials exists such that their dependency graph is degenerate, would solve an interesting open problem. This graph is defined on $n$ vertices such that $ij\in E$ if $p_i$ depends on $x_j$ or $p_j$ depends on $x_i$.

domotorp
  • 18.9k
  • 3
  • 57
  • 127