1
$\begingroup$

$(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$. A graph is $d$-degenerate if its vertices can be ordered such that from each vertex $v_i$ there are at most $d$ edges to vertices coming after $v_i$ in this ordering. In our problem $d$ can be any constant, compared to which $q$ and $n$ can be arbitrary.

$\endgroup$
11
  • 3
    $\begingroup$ by $\equiv 0$ you mean that all values are 0? As a polynomial, this is not identical 0. $\endgroup$ Commented Aug 4, 2021 at 8:34
  • $\begingroup$ I thought that $x^q-x\equiv 0$ over $\mathbb F_q$. So I mean it like that. $\endgroup$
    – domotorp
    Commented Aug 4, 2021 at 9:41
  • $\begingroup$ Ok, I see (I prefer another notation, but it is a matter of taste.) What do you mean by "dependency graph is degenerate"? $\endgroup$ Commented Aug 4, 2021 at 10:11
  • $\begingroup$ ok and which graph is degenerate? $\endgroup$ Commented Aug 4, 2021 at 11:14
  • 1
    $\begingroup$ I mean, when is a graph called degenerate? $\endgroup$ Commented Aug 4, 2021 at 13:39

0

You must log in to answer this question.

Browse other questions tagged .