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
    Nov 25, 2014 at 18:07
  • 3
    $\begingroup$ So an example would be $f_i(x) = x_i$, right? $\endgroup$
    – Vít Tuček
    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
    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
    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
    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
    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
    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
    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
    Dec 1, 2014 at 17:24
  • 2
    $\begingroup$ @PeterMueller Thanks! Okay, now we need to deal with $n>2$. $\endgroup$
    – David E Speyer
    Dec 1, 2014 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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