The Stupid Computer Problem : can every polynomial be written with only one $x$?

Solution 1:

First, let's assume that Schanuel's conjecture is true and speak very loosely. :)

Timothy Chow's 1999 article What is a Closed-Form Number? proves that the exponential and logarithm functions don't really help us to express algebraic numbers. Any algebraic number that can be expressed using those functions can also be expressed using only radicals. This is stated as Corollary 1 at the top of page 444.

So the expression $x^5-x$ can't be rewritten with a single $x$ using exponentials and logarithms. If it could, we would be able to solve the equation $x^5-x=1$ by inverting those functions, which means we could solve it using radicals, which is impossible.

Can we do without Schanuel's conjecture? Maybe. Chow hints at partial results that don't need the conjecture:

It is folklore that general polynomial equations (i.e., those with variable coefficients) cannot be solved in terms of the exponential and logarithmic functions, although nobody seems to have written down a complete proof; partial proofs may be found in [C. Jordan, Traité des Substitutions et des Équations Algébriques, Gauthier-Villars, 1870, paragraph 513] and [V. B. Alekseev, Abel's Theorem in Problems and Solutions, Izdat. "Nauka," 1976 (Russian), p. 114].

I haven't tracked down those references. Maybe there's an equation where only the 0th coefficient is a variable, like $x^5-x+C=0$, that can't be solved in the relevant way. I'm not necessarily gunning for the bounty, so perhaps someone else can pick up the story from there?

Solution 2:

$f(x) = x^{3} - x$ is a counter-example. Assume for contradiction that there exist $\alpha, \beta \in\mathbb{R}, n \in \mathbb{Z}$ such that $f(x) = (x + \alpha)^{n} + \beta$. Since $f(x)$ has degree $3$, we know $n = 3$. So $f(x) = x^{3} + 3 \alpha x^{2} + 3 \alpha^{2} x + ( \alpha^{3} + \beta) $. If $\alpha \neq 0$, then we have an $x^{2}$ term, and if $\alpha = 0$, then we have $x^{3} + \beta$. Neither works, so it cannot be written as such.

Solution 3:

Can really a Stupid Computer do everything a Super Computer can ?

This is sort of an open-ended question. Here are some interpretations I have of it.

Can the ring of polynomials over $\mathbb{R}$ be represented as a power of a polynomial of degree one plus some constant.

Any expression using the field operations on $\mathbb{R}$ and writing $x$ only once can be reduced to some polynomial of the form

$$ (ax^m + b)^n + c $$

This is pretty straightforward to check, so I'll let you do that. The answer to this question is then no, as pointed out by user AJY in another answer.

edit: I made an error above as pointed out by user David Speyer in the comments below.

Are we limited in what calculations we can do with Stupid Computer™?

Well, polynomials can be represented just as a sequence of coefficients, so there's actually no need to write $x$ at all!

Each polynomial might have a real root. If we look at the set of all polynomials and the collection of all possible roots, is this root set the same for both Stupid Computer™ and Super Computer™?

Yes. If our polynomial coefficients are in $\mathbb{R}$ then it's not a realistic computer and trivially true since for any desired root $a$, the degree 1 polynomial $x-a$ has precisely the root we want.

However, this is even true if our coefficients are in $\mathbb{Q}$! The set of all real roots for all polynomials is just a linear combination of elements of $\mathbb{Q}$ and roots thereof.