wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Thin sets for integer functions
        
(Message started by: Pietro K.C. on Oct 16^th, 2007, 11:16pm)

Title: Thin sets for integer functions
Post by Pietro K.C. on Oct 16^th, 2007, 11:16pm

Let N denote the natural numbers, and let

f : N² ---> N

be any function. Prove that there is an infinite set A, contained in N, such that f(A²) is not all of N.

Can you generalize to f : N^k ---> N? (For k=1 it's trivial.)

Title: Re: Thin sets for integer functions
Post by Eigenray on Jan 8^th, 2008, 6:51am

Well now this was tricky. I started thinking about whether it was true with only finitely many colors. For example, if we color N² using 3 colors, for {x<y}, {x=y}, and {x>y}, then clearly any infinite set A² must use all three colors. But what about 4? Will a finite number of colors suffice? Put like this, it seemed a bit like Ramsey theory:

[link=http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Infinite_Ramsey_theory]Infinite Ramsey theorem[/link] (IRT): Let X be some countably infinite set and colour the elements of X⁽ⁿ⁾ (the subsets of X of size n) in c [finite!] different colours. Then there exists some infinite subset M of X such that the size n subsets of M all have the same colour.

Now we can use this to prove the following: if f:N² http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif{1,2,3,4}, then there is an infinite subset A http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subseteq.gif N such that f(A²) misses a value (and as we saw above, this is optimal).

For a<b, define f_i : N⁽²⁾ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif {1,2,3,4} by f₁({a,b})=f(a,b), f₂({a,b})=f(b,a), and f₃({a,b})=f(a,a).

By IRT, we can pick an infinite set M₁ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subset.gif N such that f₁(M₁⁽²⁾) = {x} is a single value. Now, restricting f₂ to M₁⁽²⁾, we again use IRT to pick an infinite subset M₂ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subset.gif M₁ such that f₂(M₂⁽²⁾) = {y} for some y, and then finally A http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subset.gif M₂ with f₃(A⁽²⁾) = {z}.

Now if (a,b) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif A², either a < b, a > b, or a = b. In the first case, f(a,b) = f₁({a,b}) = x; in the second, f(a,b) = f₂({a,b}) = y. And in the third case we can pick b' http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif A with b' > a, so that f(a,a) = f₃({a,b'}) = z. So f(A²) = {x,y,z}.

For arbitrary k, we can show that if f : N^k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif {1,2,...,R+1}, then we can pick A such that f(A^k) misses a value, where R is the number of ways to rank k things (allowing ties). That is, we define R functions h_i : N^(k) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif N^k, one using each order type, so that for any element (x₁,...,x_k) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif N^k, we have that for some i, h_i({x₁,...,x_k} = (x₁,...,x_k), roughly speaking. The complication is that if {x₁,...,x_k} contains fewer than k elements, we can pad the set with sufficiently large numbers. Then take f_i = f h_i and argue as before.

For example, with k=3, and x<y<z, we might have
h₁({x,y,z}) = (x,y,z),
h₂({x,y,z}) = (x,z,y),
...
h₆({x,y,z}) = (z,y,x),

easy enough. Then we have to consider rankings where two are the same, say a<(b=c). This leads to
h₇({x,y,z}) = (x,y,y),
so that (a,b,c) = h₇({a,b,large}). Or if b < (a=c), we do
h₈({x,y,z}) = (y,x,y),
so that (a,b,c) = h₈({b,a,large}).
Finally
h₁₃({x,y,z}) = (x,x,x).

In general: if T is the order type where
a₁,...,a_k take on r distinct values, say v₁ < ... < v_r, we would set the corresponding

h_T({x₁<x₂<...<x_k}) = (x_j1,...,x_jk),

where j_i http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif {1,...,r} is defined by a_i = v_ji. Clearly the definition of h_T only depends on the order type T.

Now by construction, if the k-tuple (a₁,...,a_k) has order type T, then for L₁,...,L_k-r large enough (bigger than v_r), if we sort the set

S={a₁,...,a_k,L₁,...,L_k-r} = {v₁ < v₂ < ... < v_r < L₁ < ... < L_k-r},

we get by definition

h_T(S) = (v_j1,...,v_jk) = (a₁,...,a_k).

[I don't know if that actually makes it any clearer, but I needed to write it out to convince myself!]

Now of course if f : N^k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif U, where U is any set with more than R elements, then we can pick a surjection s : U http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif {1,...,R+1}, and find that sf misses a value, so f did as well.

Title: Re: Thin sets for integer functions
Post by Grimbal on Jan 8^th, 2008, 7:03am

on 10/16/07 at 23:16:14, Pietro K.C. wrote:

Prove that there is an infinite set A, contained in N, such that f(A²) is not all of N.

Is f(A²) = { f(a,b) | a, b in A } ?

Title: Re: Thin sets for integer functions
Post by Eigenray on Jan 8^th, 2008, 7:13am

on 01/08/08 at 07:03:26, Grimbal wrote:

Is f(A²) = { f(a,b) | a, b in A } ?

Yes, as a corollary of A² = {(a,b) | a,b in A}, and f(S) = { f(x) | x in S }.