How to prove that two univariate polynomials(over any field) are always algebraically dependent? Also, how to prove the generalization of this question i.e if number of polynomials are more than number of variables then those polynomials are always algebraically dependent?I know one proof, but still posting this question because i want to know about alternative proofs of this nice fact. The proof i know is this :if those n+1 polynomials are independent then they will form a transcendence base of $k(x_1,..x_n)/k$ and it's dimension will be n+1. but {$x_1,...x_n$} is a transcendence basis for $k(x_1,..x_n)/k$ and its dimension is n. But dimension of two transcendence bases should be same. So contradiction. My guess is this elementary fact can be proved by many different ways.

1$\begingroup$ If you're going to do this, the way to do it is to give your proof, so we don't waste our time and yours by telling you something you already know. $\endgroup$ – Gerry Myerson Dec 8 '14 at 11:09

$\begingroup$ Sorry. Now, i added what i know. $\endgroup$ – Adam Dec 8 '14 at 12:02
Here is an elementary proof for the case of univariate polynomials. Let $f, g \in F[x]$, where $F$ is your field, with $\deg(f) = m$, $\deg(g) = n$. Then $f^k g^l$ has degree $km + ln$. For $0 \le k \le N/(2m)$, $0 \le l \le N/(2n)$, this degree is $\le N$. So there are $\ge N^2/(4mn)$ expressions $f^k g^l$ of degree $\le N$, and they live in an $F$vector space of dimension $N+1$. If $N$ is sufficiently large, then the number of elements you get in this space is larger than its dimension, so they must be linearly dependent. This gives you an algebraic relation between $f$ and $g$.
This generalizes to polynomials in arbitrarily many variables.

$\begingroup$ You meant "$\ge N^2/(4mn)$ expressions"? $\endgroup$ – Yaakov Baruch Dec 11 '14 at 8:37

$\begingroup$ @Yaakov Baruch: "$\gg N^2$" means "$\ge c N^2$ for some constant $c$". One can take $c = 1/(4mn)$ (or even $1/(2mn)$) here, but the important point is that whatever $c$ is, this grows faster than $N+1$. $\endgroup$ – Michael Stoll Dec 11 '14 at 9:15

$\begingroup$ Ah yes  thank you. Somehow over the years I got used to $>>$ meaning "far greater". $\endgroup$ – Yaakov Baruch Dec 11 '14 at 9:39

$\begingroup$ Thinking about it, I guess both uses are common. I'll edit the answer to eliminate the ambiguity. $\endgroup$ – Michael Stoll Dec 11 '14 at 10:13
I think there's also a more explicit symmetrybased/computational approach (compared to Michael Stoll's linear algebra approach). EDIT 12/13/14: "computational" was the wrong choice of word.
For the $n=1$ (univariate) case this is a problem from (Michael) Artin's Algebra previously discussed on MSE here. Given $f,g\in k[T]$, we want a polynomial $P\in k[X,Y]$ such that $P(a,b) = 0$ (here $a,b\in \overline{k}$ are any points in the (infinite) algebraic closure of $k$) if and only if there exists $t\in \overline{k}$ such that $f(t)  a = g(t)  b = 0$. This latter condition is, by the "product of differences of roots" definition of the resultant (which for fixed $a,b$ has $k[a,b]$coefficients by the fundamental theorem of symmetric polynomials), equivalent to the (formal) vanishing of the resultant of $f(T)  X$ and $g(T)  Y$, which is a polynomial in $k[X,Y]$.
If I'm not mistaken, this should generalize via the multivariate resultant: see Wikipedia or this paper ("Explicit formulas for the multivariate resultant" by Carlos D'Andrea and Alicia Dickenstein).
[BTW, I believe that at least in the univariate case, combining the above with another exercise in Artin shows that if $k = \overline{k}$ is algebraically closed and $f,g$ are not both constant, then (0) the ideal of working polynomials $P$ is principal, and if $m$ is a generator (unique up to scaling), then (1) $m$ is irreducible in $k[X,Y]$; (2) for $(a,b)\in k^2$, we have $m(a,b) = 0$ iff there exists $t\in k$ with $(x(t),y(t)) = (a,b)$; and (3) the resultant is (up to scaling) a power of $m$.
(0,1) can be proven by standard means (e.g. Bezout's identity in the PID $k(Y)[X]$; I'm told this is really a dimension theory argument)one might only need that $k$ is infinite, not algebraically closedand (2,3) by looking at the resultant ($k = \overline{k}$ is important here). I don't think Hilbert's nullstellensatz is necessary.]

6$\begingroup$ M.Stoll's suggestion is computational. For example, in the univariate case the resultant is exactly the determinant you get when you first have as many equations as variables. $\endgroup$ – Noam D. Elkies Dec 11 '14 at 3:26

$\begingroup$ Agreed it's computational; apologies for my poor wording above. But more importantly, I'm confused about your "first working determinant = resultant" construction. First off, I do believe it for $f = g = T^1$: we have an original $2\times 3$ matrix with "$T^1$ coeff. row" $[1,1,0]$; "$T^0$ coeff. row" $[0,0,1]$. If we append the extra row $[X,Y,1]$, the $3\times 3$ determinant via minor expansion along the bottom (extra) row gives a working polynomial; in this case it happens to be the resultant. $\endgroup$ – Victor Wang Dec 14 '14 at 5:04

$\begingroup$ In general, however, the resultant of $f(T)  X, g(T)  Y$ has $\max(km + ln) = mn$ over its nonzero $X^k Y^l$ terms (max. achieved at $X^n$, $Y^m$). But $km + ln \le mn$ has only $\approx \frac12 mn$ solutions for large $m,n$. So if we choose $N$ just large enough so that we "first have as many eqs as vars", i.e. $km+ln \le N$ first has around $N$ sols, then $N  mn$ is large. So I feel the determinant approach can only a priori guarantee a multiple of the resultant, unless there happens to be some very mysterious additional structure in the determinant. $\endgroup$ – Victor Wang Dec 14 '14 at 5:10
For polynomials over the field of complex numbers $\mathbb{C}$ there is yet another method. Namely, polynomials in $m$ variables with coefficients over $\mathbb{C}$ can be considered as meromorphic functions on the complex projective space $\mathbb{CP}^m$. To prove algebraic dependence of $k$ polynomials with $k > m$ (as a trivial corollary) one can use the following (nontrivial) theorem due to C. L. Siegel and W. Thimm: Let $X$ be a compact connected complex manifold. The functions $f_1,...,f_k$ meromorphic on $X$ are algebraically dependent if and only if they are analytically dependent (i.e., $df_1(x)\wedge...\wedge f_k(x)=0$ at every point $x \in X$ where all $f_1,...f_k$ are holomorphic). The proof of the SiegelThimm theorem can be found e.g. in ``Holomorphic Morse Inequalities and Bergman Kernels" by Xiaonan Ma and George Marinescu, Birkh\"auser, Basel 2007 (Theorem 2.2.9).

2$\begingroup$ Actually, the way Ma and Marinescu prove this theorem of Siegel, consists in considering the map $K[T_1,...,T_k]\to \mathscr M(X)$ induced by the $f_i$, and to show that it cannot be injective if $k>\dim(X)$ by inspecting its jets at a nondegenerate point $x$, making use of the Schwarz lemma. It is thus very close to Michael Stoll's approach which can be thought of as a kind of babycase. $\endgroup$ – ACL Dec 11 '14 at 7:44