28
$\begingroup$

Let $f_{1},f_{2},\ldots,f_{n}$ be $n$ polynomials in $\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{n}]$ such that $\forall a=(a_1,a_2,\ldots,a_n)\in\mathbb{F}_{2}^{n}$ we have $\forall i\in[n]:f_{i}(a)=a_{i}$.

Can $f_{i}$'s be algebraically dependent over $\mathbb{F}_{2}$?.

Or even, can we say something about lower bound on the transcendence degree of this set $\{f_{1},f_{2},\ldots,f_{n}\}$ of polynomials over $\mathbb{F}_{2}$?

Improve this question
$\endgroup$
12
  • $\begingroup$ What does the restriction $f_i(a)=a_i$ mean? What are $a_i$? $\endgroup$
    – Alex Degtyarev
    Commented Nov 25, 2014 at 18:07
  • 3
    $\begingroup$ So an example would be $f_i(x) = x_i$, right? $\endgroup$
    – Vít Tuček
    Commented Nov 28, 2014 at 14:34
  • 1
    $\begingroup$ @Turbo The question is whether there is another polynomial $0 \neq g \in \mathbb{F}_2[x_1, \ldots, x_n]$ such that $g(f_1, \ldots, f_n)=0$. $\endgroup$
    – Peter Arndt
    Commented Nov 30, 2014 at 14:25
  • 2
    $\begingroup$ @joro The question is whether the resulting polynomial is zero itself, not whether it represents the constant function with value zero. $\endgroup$
    – Peter Arndt
    Commented Dec 1, 2014 at 12:39
  • 3
    $\begingroup$ @joro See my last comment: These are non-zero polynomials, which happen to represent the zero function. But the question of algebraic dependence is whether one can produce the zero polynomial. $\endgroup$
    – Peter Arndt
    Commented Dec 1, 2014 at 15:17

1 Answer 1

Reset to default
23
+50
$\begingroup$

Not for $n=2$. I'm afraid this answer uses a lot more algebraic geometry than the question; I spent some time trying to remove it and failed.

Suppose, for the sake of contradiction, that $f_1$ and $f_2$ obey a polynomial relation $g(x,y)$. Let $X$ be the curve $g(x,y) = 0$ in $\overline{\mathbb{F}_2}^2$ (the algebraic closure of $\mathbb{F}_2$) and let $\tilde{X}$ be its normalization. So $(f_1, f_2)$ gives a map $\mathbb{A}^2 \to X$ which, since $\mathbb{A}^2$ is normal, must factor through $\tilde{X}$.

This describes $\tilde{X}$ as the image of a rational variety, so $\tilde{X}$ is unirational. For curves, unirational is the same as rational. So $X$ is a genus zero curve (with some number of punctures.) But a genus zero curve defined over $\mathbb{F}_2$ can have at most three $\mathbb{F}_2$-points, so the map $\mathbb{A}^2 \to \tilde{X}$ must identify two of the four $\mathbb{F}_2$-points of $\mathbb{A}^2$. This contradicts that these points are supposed to have distinct images under the composition $\mathbb{A}^2 \to \tilde{X} \to X \subset \mathbb{A}^2$.

I see no reason the result should hold for $n=3$, and have played a little with a counterexample where $\mathbb{A}^3$ maps to a cubic surface, but I haven't found an example yet. For example, $x^2 y + x y^2 + z^2 + z$ is a smooth cubic that passes through all eight points of $(\mathbb{F}_2)^3$ (and even remains a smooth cubic in $\mathbb{P}^2$ through all fifteen points of $\mathbb{P^2}(\mathbb{F}_2)$); I see no reason that we couldn't map $\mathbb{A}^3$ to it.

Observation: The key question is whether there is a polynomial map $\mathbb{A}^n \to \mathbb{A}^N$, for any $N$, which is defined over $\mathbb{F}_2$, has $(n-1)$-dimensional image and is injective on $\mathbb{F}_2^n$. If so, we can easily interpolate $n$ polynomials in $N$ variables so that the composite $\mathbb{A}^n \to \mathbb{A}^N \to \mathbb{A}^n$ is the identity on $\mathbb{F}_2^n$.

Improve this answer
$\endgroup$
16
  • 8
    $\begingroup$ This proof can be elementarized quite a bit: If $f_1$ and $f_2$ are algebraically dependent, then $\mathbb F_2(f_1,f_2)\subseteq\mathbb F_2(x_1,x_2)$ has transcendence degree $1$ over $\mathbb F_2$. By Theorem 4, Chapter 1 in Schinzel's book `Polynomials with special regard to reducibility', there is a polynomial $g\in\mathbb F_2[x_1,x_2]$ with $\mathbb F_2(f_1,f_2)=\mathbb F_2(g)$. So $f_i=h_i(g(x_1,x_2))$ for univariate polynomials $h_i$. In particular, the pairs $(f_1(a),f_2(a))$ assume at most $2$ different values, while the assumption requires $4$ values. $\endgroup$
    – Peter Mueller
    Commented Dec 1, 2014 at 11:49
  • 1
    $\begingroup$ ... continued: The proof of the background result in Schinzel is quite elementary, like the direct field theoretic proofs of Lüroth's Theorem. $\endgroup$
    – Peter Mueller
    Commented Dec 1, 2014 at 11:51
  • 2
    $\begingroup$ @eig There are two flaws with this argument. The first is that unirational (what you can deduce from being a subfield of $\mathbb{F}_2(x_1, \ldots, x_n)$) is weaker than rational (isomorphic to $\mathbb{F}_2(g_1, \ldots, g_{n-1})$) once $n>2$. See en.wikipedia.org/wiki/Zariski_surface . $\endgroup$
    – David E Speyer
    Commented Dec 1, 2014 at 15:22
  • 4
    $\begingroup$ @David: If $h(g(x))$ is a polynomial, where $g$ is a polynomial and $h$ is a rational function, then $h$ is actually a polynomial. (Write $h(z)=p(z)/q(z)$, then $1=u(z)p(z)+v(z)q(z)$ by Bezout, so $1=u(g(x))p(g(x))+v(g(x))q(g(x))$, thus the numerator and denominator of $p(g(x))/q(g(x))$ are relatively prime, so $q$ is a constant.) $\endgroup$
    – Peter Mueller
    Commented Dec 1, 2014 at 17:24
  • 2
    $\begingroup$ @PeterMueller Thanks! Okay, now we need to deal with $n>2$. $\endgroup$
    – David E Speyer
    Commented Dec 1, 2014 at 19:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .