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}$?

$\endgroup$
  • $\begingroup$ What does the restriction $f_i(a)=a_i$ mean? What are $a_i$? $\endgroup$ – Alex Degtyarev Nov 25 '14 at 18:07
  • 3
    $\begingroup$ So an example would be $f_i(x) = x_i$, right? $\endgroup$ – Vít Tuček Nov 28 '14 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 Nov 30 '14 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 Dec 1 '14 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 Dec 1 '14 at 15:17
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$.

| cite | improve this answer | |
$\endgroup$
  • 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 Dec 1 '14 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 Dec 1 '14 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 Dec 1 '14 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 Dec 1 '14 at 17:24
  • 2
    $\begingroup$ @PeterMueller Thanks! Okay, now we need to deal with $n>2$. $\endgroup$ – David E Speyer Dec 1 '14 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.