# Are polynomials with integer coefficients uniquely determined by their coefficients?

Assume f and g are polynomials, where f = g. More explicitly;

$$f = a_{n}z^{n} + \ldots + a_{1}z + a_{0} = b_{n}z^{n} + \ldots + b_{1}z + b_{0} = g$$

where $\ \ a_{0} \ , \ldots, \ a_{n} \in \mathbb {Z}, \ and \ z \in \mathbb{C}$

then $$a_{0} = b_{0} \ , \ldots, \ a_{n} = b_{n}$$

Attempted proof:

$f - g = 0$, thus we can now equate coefficients;

i.e. $$a_{0} - b_{0} = 0 \ , \ldots, \ a_{n} - b_{n} = 0$$

$$\implies a_{0} = b_{0} \ , \ldots, \ a_{n} = b_{n}$$

$\square$

So, is this essentially stating that polynomials are uniquely determined by there coefficients?

This question is spurred as I am trying to prove that the set of all algebraic numbers is countable, and consequently my proof will in turn rely upon such a statement as this, since if each polynomial is uniquely determined in this manner, then we should be able to find some (not exactly sure if it will be an isomorphism or just a monomorphism?) correspondence between the set of all polynomials with integer coefficients of degree n and the set of all n-tuples with integer components.

I believe we can then show that this set of all n-tuples with integer coefficients will be countable, because it will be the cartesian product:

$$\mathbb{Z} \times \ldots \times \ \mathbb{Z} \cong \mathbb{Z}^{n}$$

and the finite cartesian product of countable sets is countable. We then can see that the set of all polynomials with integer coefficients is countable, which i feel puts me a step closer to solving said problem.

I feel that given this to be true, then as all polynomials only have a finite number of zeroes, we can use that the countable union of finite sets is countable to finish the proof.

Does this seem like a feasible plan for proving the statement?

• The general strategy is fine. For any $n$ the set of algebraic numbers of degree $\le n$ is countable, and the union of countably many countable sets is countable. There is an implicit appeal to the Axiom of Choice. With a little care it can be bypassed. – André Nicolas Oct 31 '15 at 3:56
• Thank you André. Can this appeal to the axiom of choice be restrictive in some manner? Why would one wish to bypass its use? – D.S. Oct 31 '15 at 4:33
• Some people do not accept AC, though most accept at least the weak version needed here. Even if one accepts AC, an argument can be made that an AC-free proof is more informative. – André Nicolas Oct 31 '15 at 4:37

If $f(x)=g(x)$ as functions, then set $h(x)=f(x)-g(x)$, a polynomial since $f,g$ are. Since $f=g$ as functions, $h(x)$ is identically zero, i.e. zero for every $x$. If $h(x)$ isn't the zero polynomial, then it has some degree, say $m$. But then it would have at most $m$ complex zeroes. But $h(x)$ has infinitely many zeroes. Hence $h(x)$ must be the zero polynomial, so in fact the coefficients of $f,g$ must be identical.

• Thank you. Now you state that ${h(x)}$ has infinitely many zeroes. Why can we claim this without appealing to the fact that h attains zero coefficient for every x? Or can this be used? and if yes, why? – D.S. Oct 31 '15 at 4:14
• Because for every $a$, $h(a)=f(a)-g(a)=0$. – vadim123 Oct 31 '15 at 4:19

A polynomial as algebraic entity, contrary to the polynomial function, is defined as the sequence of its coefficients. That way your question does not arise.

Thus the real question should be: while mapping polynomials to polynomial functions, is there more than one way to obtain the zero function? And yes, in general there is, for instance for polynomials over $\Bbb Z_2$. But not for polynomial over fields of characteristic $0$.

But does that really matter for your question? If two different polynomials have the same root, then you have some roots multiply counted (that will happen anyway if you are not able to restrict the set of polynomials to irreducible ones). So less roots than your bound, but that may happen anyway if the bound is not exact. Inexact bounds are often less work.

We can show that the set of algebraic numbers is countable without AC (the Axiom of Choice) as follows :

1. Proving that $\cup_{n\in \mathbb N} \mathbb Z^n$ is countable does not require AC.

2. A set $T$ is Tarski-finite iff there exists $m\in \mathbb N$ and a bijection $f:T\to \{a\in N:a<m\}.$

1. Lemma 1. If $m\in \mathbb N$ and $T=\{T_a : m>a\in \mathbb N\}$ is a family of Tarski-finite sets then $\cup T$ is Tarski-finite. PROOF: Use induction on $m.$

4.(a) A subset of a Tarski-finite set is Tarski-finite. (b). A linear order on a Tarski-finite set is a well-order.

1. Lemma 2. Let $S=\{S_n: n\in \mathbb N\}$ be a family of Tarski-finite sets. If $\cup S$ can be linearly ordered then $\cup S$ is countable.

PROOF: Let $<_S$ be a linear order on $\cup S.$ For $x\in \cup S$ let $g(x)=\min \{n:x\in S_n\}.$ For $x,y\in \cup S$ with $x\ne y,$ define $$x<_Wy\iff ((g(x)<g(y))\lor (g(x)=g(y)\land x<_Sy)).$$ We may easily confirm that $<_W$ is a well-order. And for any $x \in \cup S$ the set $pred_{<_W}x=\{y\in \cup S:y<_W x\}$ is a subset of $\cup \{S_n :n\leq g(x)\},$ which by Lemma 1, and by 4.(a) , is Tarski-finite. So $<_W$ is isomorphic to the natural order on $\mathbb N$ or on a finite initial segment of $\mathbb N.$

2. For real $x,y,x',y'$ define $x+iy <_S x'+iy' \iff ((x<x')\lor (x=x'\land y<y').$ Then $<_S$ is a linear order. Applying (1), let $\{P_n :n\in \mathbb N\}$ be the set of all complex polynomials whose co-efficients are not all $0.$ For each $n,$ let $S_n$ be the set of solutions of $P_n(z)=0.$ Each $S_n$ is Tarski-finite and the set $\mathbb A$ of algebraic numbers, which is $\cup \{S_n:n\in \mathbb N\},$ is linearly ordered by $<_S$. So $\mathbb A$ is countable by Lemma 2.

Remark. Re Lemma 2 (paragraph 5). To show that the linear order $<_W$ is a well-order : For $\emptyset \ne T\subset S,$ let $n_0=\min \{n: \exists x\in T\;(g(x)=n)\}.$ And let $y=\min_{<_S}T\cap S_{n_0},$ which exists by 4(b). Then $y=\min_{<_W}T.$