VTRMC 1979 Problem 8

Let $S$ be a finite set of polynomials in two variables, $x$ and $y$ . For $n$ a positive integer, define $\Omega _ { n } ( S )$ to be the collection of all expressions $p _ { 1 } p _ { 2 } \dots p _ { k } ,$ where $p_i \in S$ and $1\leq k \leq n$ . Let $d_n(S)$ indicate the maximum number of linearly independent polynomials in $\Omega _ { n } ( S )$ . For example, $\Omega _ { 2 } \left( \left\{ x ^ { 2 } , y \right\} \right) = \left\{ x ^ { 2 } , y , x ^ { 2 } y , x ^ { 4 } , y ^ { 2 } \right\}$ and $d _ { 2 } \left( \left\{ x ^ { 2 } , y \right\} \right) = 5$ (a) Find $d _ { 2 } ( \{ 1 , x , x + 1 , y \} )$ . (b) Find a closed formula in $n$ for $d _ { n } ( \{ 1 , x , y \} )$ . (c) Calculate the least upper bound over all such sets of $\overline{\text{lim}} _ { n \rightarrow \infty } \frac { \log d _ { n } ( S ) } { \log n }$ ( $\overline{\text{lim}} _ { n \rightarrow \infty } a _ { n } = \lim _ { n \rightarrow \infty } ( \sup \left\{ a _ { n } , a _ { n + 1 } , \ldots \right\}$ , where sup means supremum or least upper bound.)