MathDB

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.)

Problem Statement