Skip to main content
added definition of degenerate
Source Link
domotorp
  • 18.9k
  • 3
  • 57
  • 127

$(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.

$(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$.

$(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.

added def of dependency graph
Source Link
domotorp
  • 18.9k
  • 3
  • 57
  • 127

$(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$.

$(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.

$(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$.

Source Link
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.