Do we really need polynomials (In contrast to polynomial functions)? In the following I'm going to call


*

*a polynomial expression an element of a suitable algebraic structure (for example a ring, since it has an addition and a multiplication)
that has the form $a_{n}x^{n}+\cdots+a_{1}x+a_{0}$, where $x$ is
some fixed element of said structure,    

*a polynomial function a function of the form $x\mapsto a_{n}x^{n}+\cdots+a_{1}x+a_{0}$ (where the same algebraic considerations as above apply)

*a polynomial an element of the form $a_{n}X^{n}+\cdots+a_{1}X+a_{0}$ with indeterminates $X$ (these
can be formalized, if we are in a ring, with strings of $0$s and
a $1$).
Note that when we are very rigorous/formal, polynomial expressions
and polynomials are something different (although in daily life we
often use them synonymously). Polynomial functions and expressions
are also different from each other although in this case the relationship
is a closer one, since every polynomials expression can be interpreted
as a polynomial function evaluated at a certain point (thus "polynomial
functions" are something more general than "polynomial expressions").
My question is: Why do we use polynomials ? It seems to me that every
piece of mathematics I have encountered so far, one could replace
every occurrence of polynomials with polynomial expressions/functions
without any major change in the rest of the proof/theorem/definition
etc.
The only reasons that I can see to use polynomials are the following
two:$$ $$
1. After one makes the idea precise that one can plug "suitable"
elements into polynomials (which may lie a ring containing the ring
in which the coefficients live in), one can save time in certain setting,
by handling the "plugging of suitable elements into polynomials"
more elegantly: For example in case of the theorem of Cayley-Hamilton,
which in its "polynomial function" version would look like:
Let $A$ be an $n\times n$ matrix over $K$, whose characteristic
polynomial (function) is $x\mapsto a_{n}x^{n}+\cdots+a_{1}x+a_{0}$.
Then 
$$
a_{n}A^{n}+\cdots+a_{1}A+a_{0}I=0.
$$
whereas the "polynomial" version looks more elegant:
Let $A$ be an $n\times n$ matrix over $K$, whose characteristic
polynomial is $p_{A}\in K\left[X\right]$. Then 
$$
p_{A}\left(A\right)=0.
$$
2. The only thing that polynomials can "do", but algebraic expressions/functions can't, is to be different, when the algebraic expressions/functions are the same (i.e. there's a theorem that tells us that the mapping of polynomials to polynomials expressions/functions
isn't injective, if the field is finite). Maybe this small difference makes a big enough difference
to consider polynomials after all, but as I said, I haven't encountered
any situation in which this difference could manifest itself.
(I'm guessing that maybe cryptography or higher number theory really needs
polynomials and not just polynomial expressions/functions. Since I don't know
anything about these subjects, I would be very happy with an example
of a theorem (whose content isn't merely technical as it is the case with the theorem above) involving polynomials, where these absolutely cannot
be replaced by polynomial expressions/functions. Conversely I would also be happy with an authoritative statement from someone knowledgeable that indeed we could dispense of polynomials, if we wanted to.)
 A: Constructing field extensions is a very important operation. This is most conveniently done as follows: Let $F$ be a field and $p(X)\in F[X]$. Suppose we wish to adjoin to $F$ an element $\alpha$ that will satisfy a certain algebraic equation. That is, there is a polynomial $P(X)\in F[X]$ such that we wish $P(\alpha)=0$ (notice here we switched between the polynomial $P(X)$ and its associated function evaluated at $\alpha$). If $P(X)$ is irreducible, then such a field extension is constructed as $F[X]/(P(X))$. It is crucial for this construction to take $F[X]$ to be the ring of polynomials, not polynomial functions. 
Another reason is the convenient fact that a ring homomorphism $R[X]\to S$, from the ring of polynomials with coefficients in $R$ to a ring $S$, is the same thing as a homomorphism $R\to S$ together with a choice of an arbitrary element in $S$. Thus, polynomial rings allow for a systematic study of homomorphism+an element. It turns out that many properties of the chosen element are reflected by properties of the homomorphism, which in turn are related to properties of the domain, that is of polynomials (not polynomial functions). 
One more reason is that polynomials are combinatorial beasts. They can be manipulated purely combinatorially. But since they give rise to functions, it means that we can use combinatorics to study functions. For instance, given functions $f,g$, can you find functions $a,b$ such that $af+bg=1$ is quite easily solved using the Euclidean algorithm if all these functions are required to be polynomials (the solution is actually constructive).
A: Here are some answers with somewhat different conclusions.  Let us call the form of polynomials with coefficients and indeterminates "abstract" or "algebraic" to distinguish them from polynomial functions.
If you want to work with rational functions, the situation becomes foggy if you do not define everything in terms of abstract polynomials:


*

*Is the function $f(x) = +\frac{1}{x} \ -\frac{1}{x}$ equal to the zero function?

*Is $\frac{x}{x}$ equal to $1$ for all $x$, or only for $x \neq 0$?

*When composing a chain of linear fractional functions $\frac{ax+b}{cx+d}$ do we exclude more and more points from the domain everywhere that one of the denominators is zero, when the end result as a rational function has at most one one singularity? Over a finite field this can empty the domain of all its points.

*For an infinite field you can get around some of this by treating polynomial functions and rational functions as function-equal if they are equal at infinitely many points, and defining rational functions as written in lowest terms (which breaks the analogy with fractions).  Over a finite field, nothing like that can work because ratios like ${p(x)^a}/{p(x)^b}$ are not defined if $p=0$ for all elements in the finite field, and if there were a way to define it based on functions (such as using the lowest-degree representation) it would not depend on the exponents. 


In the other direction:


*

*if you want representations of the polynomial to not always be centered at $0$ or to be less coordinate dependent, then you might want polynomial to mean a function killed by differential or difference operators of order $n$ for some $n > 0$.  

*where polynomials appear by a construction that operates on functions, and cannot be performed on the abstract polynomials, then you have no choice but to work with polynomials as functions.  


In algebraic uses of polynomial functions, the arithmetic operations, function composition, differentiation and integration are often sufficient and can be done on the abstract form, and a function is demonstrated to be polynomial by exhibiting an abstract form.  So the evaluation that converts algebraic representation into a function can always be postponed by doing all operations on the algebraic representation. 
A: You write that polynomial functions are "more general" than polynomial expressions. In fact the exact opposite is the case: multiple polynomial expressions may be the same function (on a finite field), so it's polynomial expressions that are more general.
Here are a few ways that polynomial expressions are useful where it could (or would) be awkward to use polynomial functions. 


*

*If $F$ is  a field of $p^r$ elements, for a prime $p$ and positive integer $r$, then $F$ is the splitting field over ${\mathbf F}_p$ of $x^{p^r} - x$. But for every $a \in F$, $a^{p^r} = a$, so $a^{p^r} - a = 0$. You don't want to say $F$ is the splitting field of, well, "zero". The distinction between the nonzero polynomial $x^{p^r} - x$ in $F[x]$ and the zero polynomial is essential for that. 

*In case you think "I don't care about finite fields", well, some properties of sequences of integers are proved by making them into the coefficients of a polynomial and then reducing the polynomial mod p, which places the polynomial into ${\mathbf F}_p[x]$, where there are convenient features that are not available in ${\mathbf Z}[x]$. One example of this is a slick proof of Lucas's congruence on binomial coefficients. It's crucial for this that we can recover the coefficients of a polynomial in ${\mathbf F}_p[x]$ even if its degree is greater than $p$, which is impossible if you think of polynomials in ${\mathbf F}_p[x]$ as functions ${\mathbf F}_p \rightarrow {\mathbf F}_p$.

*Quotient rings of $A[x]$, where $A$ is a ring, may not look like functions from an elementary point of view. Do you feel it's easier to work with ${\mathbf Q}[x]/(x^5)$ using the viewpoint of polynomials as functions rather than expressions? 

*Would you like to define the ring of noncommutative polynomials in two variables as functions?

*Generating functions are important objects in mathematics (not just in combinatorics), and they are formal power series rather than numerical series. Most of them have positive radius of convergence (assuming their coefficients are in a ring like ${\mathbf R}$ or ${\mathbf C}$ and thus have a region where it makes sense to substitute a scalar for the variable at all), so they can be treated as functions on the domain of convergence, but it is convenient that the theory of formal power series doesn't really need to rely on the radius of convergence to get off the ground. Sometimes a generating function may even have radius of convergence equal to 0 but still contain useful information that can be legally extracted because formal power series can be developed without needing a radius of convergence. Of course a lot of important intuition about the way formal power series are manipulated is inspired by the properties of classical numerical power series as functions.
Your question mentions 3 types of polynomial objects: polynomial expressions, polynomial functions, and polynomials as strings of coefficients. I'd say the first and third are really synonymous (the third is really just a rigorous form of the first, not materially different in practice), but they're not the same as polynomial functions if you work over a finite field. If the coefficients are an infinite field then different polynomial expressions do define different functions on the field.
A: If the mapping from polynomials to polynomial functions is not injective, then one cannot talk about the coefficients of a polynomial function. Without coefficients, one cannot do Euclidean division. Without Euclidean division, not much of what one does readily with polynomials over a field can be done (defining minimal polynomials of linear operators is one such thing; there are many others). In short, in algebra one works with polynomials, not with polynomial functions.
Note that the ring of polynomial functions over a finite field $F$ (which is in fact the ring of all functions $F\to F$) is not an integral domain; it is in fact a rather ugly object from the algebraic point of view (a product ring of $\#F$ copies of $F$).
However, if you want a statement from someone knowledgeable that indeed we could dispense of polynomials, note that Serge Lang in Introduction to Linear Algebra (2) Chapter IX defines polynomials over an arbitrary field $K$ as polynomial functions, and goes on stating a Theorem$~1$ that the mapping from coefficient sequences to polynomials (i.e., functions) is injective (which as observed in the question fails for finite fields). The proof of the theorem is conveniently only given for the case where $K$ is the real or complex numbers. I certainly would not want to exclude Serge Lang from the set of knowledgeable people, but it seems that in this particular instance he made a regrettable error where he should have known better.
Added: Leafing though the cited book, I recently found out a detail that might explain what Lang did. I thought I knew without having to look it up what was meant by "a field $K$"; however, in section II.2 of the book it says "Let $K$ be a subset of the complex numbers $\mathbf C$. We shall say that $K$ is a field if it satisfies the following conditions:" (requiring closure under addition, multiplication, negation and inversion of nonzero$~x$, and containment of $0,1$). The proof later given of uniqueness of polynomial coefficients is by considering the asymptotic behaviour of the polynomial function for large arguments. The proof is immediately followed by the cryptic sentences "We have used the notion of limit. In Chapter$~$XII, $\S1$ we shall prove the same statement for more general fields, by a method which is completely algebraic." This leaves me wondering what "more general" fields are intended; given the earlier definition one might assume "general subfields of $\mathbf C$", but the proof using limits would appear to do fine for any such field. Anyway I cannot see which proof is being referred to. There is corollary 3 saying that a polynomial in $K[t]$ of degree $n$ has at most $n$ roots in$~K$, but that is not the same statement. More importantly, it assumes that degree has been defined, and it uses Euclidean division; as these notions use the existence of (unique) polynomial coefficients, this would appear to be circular.
A: Over some fields, the map from polynomials to polynomial functions is not injective; for example, over the finite field $\mathbb{F}_2$, the polynomial function $x^2+x$ is the same as the $0$ function - try plugging in $0$ and $1$. So in this case the (infinite) set of polynomials over $\mathbb{F}_2$ is much larger than the (finite) set of polynomial functions $\mathbb{F}_2\to\mathbb{F}_2$.
A: OK, this is an old question, but I think the following is not covered by the other answers.
The polynomial as defined in point 3 is really a special case of the polynomial expression as defined in point 1. In particular, given the commutative ring the coefficients are from, the “suitable algebraic structure” (a commutative ring) for the polynomial is obtained as follows:


*

*All elements of the original ring are also in the extended ring, and the same relations hold between them (that is, the ring of the coefficients is a subring of the ring of polynomials).

*There's an additional element (the “unknown” you mention) that is not member of the coefficient's ring. This additional element fulfils no relations other than those implied by the axioms of commutative rings and the relations between the original elements.

*Apart of the elements mentioned above, and those additionally required to be present to make it a ring while fulfilling the condition of point 2, no further elements are added.
In this extended structure (called $R[X]$ if $R$ is the ring of the coefficients and $X$ is the name of the “unknown”), your point 3 polynomial is just the point 1 polynomial expression for the choice $x=X$.
The polynomial function can also be obtained naturally from that construction. First, we find that for any $x\in R$, there's an unique ring homomorphism* $\phi_x:R[X]\to R$ that maps $X$ to $x$ and every element of $R$ to itself. Given a polynomial $p\in R[X]$, the polynomial function then is just the function $x\mapsto \phi_x(p)$.
And for completeness, although that point was already stressed in other answers: While the polynomial uniquely determines the polynomial function (by the construction given above), the reverse is not always true.

*) A homomorphism is a function that keeps the algebraic structure intact. In particular, a ring homomorphism is a function $\phi$ with $\phi(0)=0$, $\phi(1)=1$, $\phi(a+b)=\phi(a)+\phi(b)$, $\phi(-a)=-\phi(a)$ and $\phi(ab)=\phi(a)\phi(b)$.
