# All polynomials over a finite field are sums of $2$ square-free polynomials

I quote Proposition 2.3, page 14 lines -3 and -4 of Michael Rosen's book

Number Theory in Function Fields:

Let $b_n$ be the number of square-free monics in $A= \mathbb{F}_q[t]$ of degree $n.$ Then $b_1=q$ and for $n>1$, $b_n=q^n-q^{n-1}.$

Using the proposition it is easy to prove that any polynomial $P \in A$ can be written $$P = S_1+S_2$$ where $S_1$ and $S_2$ are square-free, provided

$$q \neq 2$$

Question: What happens when $q=2.$

-
$t^2+t$ and $t^2+t+1$ cannot be written as the sum of squarefree polynomials over $\mathbb F_2$. All polynomials of degree 3 can. All non-squarefree polynomials of any degree $\geq 2$ can. No squarefree polynomial of degree 4 can. Are you looking for a complete characterization? If $P$ is squarefree, we can check that $P-f^2$ is also squarefree for various $f$ of small degree. –  Sonia Balagopalan Jan 19 '11 at 4:19
That last sentence should have been: If for a given $P$, we can check if $P−f^2$ is sq.free for a few $f$ of small degree. If it is not for some $f$, $P$ cannot be written as the sum of two sq.free polynomials. –  Sonia Balagopalan Jan 19 '11 at 4:34
Would it be cheating to let $f(t) = t^7 + 1$ and write $t^2 + t = (f + t^2) + (f + t)$? (Both $f + t^2$ and $f + t$ are square free.) –  mathic Jan 19 '11 at 5:18
@Igor Rivin: Yes, that is true. If $P$ is not sq.free, then for each sq.free polynomial $Q$ of degree $n$, we have a non-zero $P-Q$, of degree $\leq n-1$, $2^{n-1}$ in all. The number of sq.free polynomials of degree $\leq n-1$ is $2^{n-1}$. So there must be nonempty intersection. –  Sonia Balagopalan Jan 19 '11 at 21:42
@Sonia: Actually, it is possible to write the degree 4 square-free polynomials as a sum of two square-free polynomials. I did some checking in Sage, and for example $t^4 + t^3 + t^2 + t + 1 = (t^4 + t^2 + t) + (t^3 + 1)$. It looks like the only issue is with the degree 2 case, where the 'hiccup' in the powers of 2 occurs. –  mathic Jan 19 '11 at 23:42

Alright, putting together all the comments it appears to still be true when $q = 2$, depending on how you like your square-free polynomials.

First, to quote Sonia's comment, If $P$ is not sq.free, then for each sq.free polynomial $Q$ of degree $n$, we have a non-zero $P−Q$, of degree $\leq n−1$, $2^{n−1}$ in all. The number of sq.free polynomials of degree $\leq n−1$ is $2^{n−1}$. So there must be nonempty intersection. – Sonia Balagopalan

Now, suppose $P$ is square-free and has degree $n$. For any square-free polynomial of lesser degree, $Q$, $P-Q$ is a polynomial of degree $n$. There are $2 + 2 + 2^4 + \ldots + 2^{n-2} = 2^{n-1}$ choices for such $Q$, but there are only $2^{n-1}$ non-square-free polynomials of degree $n$ and we certainly did not land on $0$, so at least one of these must be another square-free polynomial of degree $n$.

So any polynomial of degree $n \geq 3$ can be written as the sum of two square free polynomials of degrees $n$ and $d$ where $d < n$. What about when $n = 2$? The only polynomials to consider are

$P_1 = t^2,$

$P_2 = t^2 + 1,$

$P_3 = t^2 + t$ and

$P_4 = t^2 + t + 1$.

If you want to add the restriction that our two square free polynomials MUST have degree at most 2, as Sonia claims, $P_3$ and $P_4$ are counterexamples. Otherwise we may write

$P_1 = (t^2 + t) + (t)$,

$P_2 = (t^2 + t) + (t + 1)$,

$P_3 = (t^2 + t^7 + 1) + (t + t^7 + 1)$ and

$P_3 = (t^2 + t^7 + t) + (t^7 + 1)$.

(Note: There is nothing too special in picking the $7$.)

Upon further thought, you can do what you want with the degree 1 polynomials. A similar trick using a larger degree polynomials will work, or you can use those as counterexamples to a restricted degree version if you like. Although trivial, you may also want to express $0$ and $1$ as sums, which can certainly be done as $z$ and $z+1$ are both square-free.

-
very nice !!!!! –  Luis H Gallardo Jan 20 '11 at 0:36