Waist on a torus

November 22, 2011 Leave a comment

Last year I worked on a interesting problem which asks about the possibility of partitioning a convex set in a plane in to {n} internally disjoint convex pieces of equal area and perimeter. The problem has since been proved when {n} is a prime power, by Aronov and Hubard and Roman Karasev for all dimensions. Here in this post I discuss a crucial lemma i worked while attempting to prove the n is a “power of two” case. In the simplest case, the lemma goes like this: given a continuous function {f:(S^{1})^{2} \rightarrow \mathrm{I\!R}} which has the {y}-antipodal property: {f(x,-y) = -f(x,y)}, there is a pair of separators of a torus along its “waist” that map to zero under {f}. More specifically, there is a subset {\Lambda} of the zero set of {f} which is such that the projection map {p_1(x,y) = x} restricted to {\Lambda} is not null homotopic. For larger powers of {2}, the notation gets a little unwieldy but the proof scales up well. Lets tackle notation first:

Label the coordinates of {(S^1)^{2^n}} in a binary system, with words using the letters {0}, {1} and {2}. The words that can be formed using these letters can be treated as vertices in a binary tree, with the word {0} as the root node. The root node has a unique child vertex as the word {1}. Other vertices consist of words {w} in letters {\{1,2\}} ( of length {<n}) each having child nodes {w1} and {w2}. For example, the binary tree for {n=3} would have vertices as below:

If we impose the dictionary ordering on such words, {0 < 1 < 2 < 11 < 12 < 21 < 22 < 111 < 222 \ldots, 12\ldots2}, then each word of length {l \le n} uniquely identifies a coordinate in {(S^1)^{2^n}}. For example, a point {x} in {S^{8}} can be written as {(x_0,x_1,x_{11},x_{12},x_{111},x_{112},x_{121},x_{122})}.

Let {W} be the set of words representing indices to coordinates of points in {(S^1)^{2^n}} that have letters in 0,1 and 2, with 0 appearing only as the starting letter and are of length not more than {n}. For each word {w \in W} of length {k\le n} we define {p_{w}:(S^1)^{2^n} \rightarrow S} to be the projection map: {p_{w}(x_0,x_1,\ldots,x_{w},\ldots) = x_{w}}. Given {w\in W}, we define a map {\omega_{w}: (S^1)^{2^n} \rightarrow (S^1)^{2^n}} as follows:

\displaystyle p_{w1w'}(\omega_{w}(x)) = x_{w2w'}, \text{ for all words} \quad w1w' \in W

\displaystyle p_{w2w'}(\omega_{w}(x)) = x_{w1w'}, \text{ for all words} \quad w2w' \in W

\displaystyle p_w(\omega_w(x)) = -x_w

and for every other word {v \in W}, {p_v( \omega_w(x)) = x_v}.

For instance, for {x \in S^{8}} and {w = 1}, we have,

\displaystyle  \omega_{1}(x) = \omega_{1}(x_0,x_1,x_{11},x_{12},x_{111},x_{112},x_{121},x_{122}) = (x_0,-x_1,x_{12},x_{11},x_{121},x_{122},x_{111},x_{112})

Thus, {\omega_{w}} changes the sign of the coordinate with index {w} and swaps coordinates with indexes {w1v} with {w2v}, leaving all the other coordinates fixed. If {w_k} represents a subword of {w} consisting of first {k} letters from {w}, then using the definition of {\omega_k}, we note in particular, that {p_{w_k}( \omega_w(x)) = x_{w_k}}. Finally let {\text{len}: W \rightarrow \mathrm{I\!N}} to be the map that gives the length of a word {w} in {W}.

Definition 1 ({w}-antipodal map) For {w \in W}, we say that a map {P:(S^1)^{2^n} \rightarrow \mathrm{I\!R}^{2^n-1}} is {w}-antipodal, if,

\displaystyle {\tilde p_w}(P(\omega_{w}(x))) = -{\tilde p_w}(P(x))

.

Theorem 2 Let {{f}: (S^1)^{2^n} \rightarrow \mathrm{I\!R}^{2^n-1}} be a continuous map with the {w}-antipodal property for each word {w \in W}. Suppose there exists {\mathbf{c} \in (S^1)^{2^n}} such that {f(\mathbf{c}) = \mathbf{0}}. Then the zero set of {f} contains a connected subset {\Lambda} which can be approximated arbitrarily closely in the Hausdorff distance by a smooth loop {L}, for which the projection map: {p_0 : L \rightarrow S^1}, {p_0(y_0,y_1,\ldots) = y_0} is not null-homotopic.

The second lemma is a Borsuk Ulam type theorem which has a cleaner and simpler proof:

Lemma 2 Let {P} be a real valued function defined on the connected closed subset {\Lambda} on the torus {(S^1)^{k}} such that projection {p_1:S^1 \times (S^1)^{k-1} \rightarrow S^1} defined by {p_1(x,\mathbf{y}) = x} is not null-homotopic. Then there exists two points {(x,\mathbf{y_1})} and {(-x,\mathbf{y_2})} in {\Lambda} such that {P(x,\mathbf{y_1}) = P(-x,\mathbf{y_2})}.

Lets tackle this in a more natural setting shall we? which is a pdf document rather than html. Here it is.

Categories: Uncategorized

q-binomials

September 17, 2011 Leave a comment

The binomial like coefficients that we saw in earlier posts:

\displaystyle  C_r^n(y) = \prod_{i=1}^r \frac{(y^{n-i+1}-1)}{y^i-1}

are called {q}-binomial coefficients. In keeping with the existing convention we will use {q} as the indeterminate instead of {y} and write {\binom{n}{r}_q} for {C_r^n(q)}

It was established in an earlier post that:

\displaystyle  \prod_{i=1}^n(y^i-1) = \prod_{i=1}^n\Phi_i(y)^{\lfloor {n/i} \rfloor}

Using this identity we may reduce the {q}-binomial coefficient to:

\displaystyle  \binom{n}{r}_q = \prod_{i=2}^n \Phi_i(q)^{\lfloor n/i \rfloor - \lfloor r/i \rfloor - \lfloor (n-r)/i \rfloor } \ \ \ \ \ (1)

We also made use of the identity:

\displaystyle  \prod_{i=0}^n(t-q^i) = \sum_{j=0}^n \binom{n}{j}_q t^{n-j+1} q^{j(j+1)/2} (-1)^j \ \ \ \ \ (2)

If we put {t=-1} in the above equation, we get

\displaystyle  \prod_{i=0}^n (1+q^i) = \sum_{j=0}^n \binom{n}{j}_q q^{j(j+1)/2}

We now discuss a few consequences of the above identities:

  1. For any natural number {n}, and { 0 < r < n}, {\binom{n}{r}_q} is divisible by {\Phi_n(q)}. For the special case where {n} is a prime, {\binom{n}{r}_q} is divisible by {(q^n-1)/(q-1)} ( for which we will use the shorter notation {[n]_q} as in wikipedia). Consequently we have,

    \displaystyle  \prod_{i=1}^n (1+q^i) -1 -q^{n (n+1)/2} = \sum_{r=1}^{n-1} \binom{n}{r}_q q^{r(r+1)/2} = 0 \mod [n]_q

    For odd primes {n=p}, {q^{p(p+1)/2} = 1} modulo {[p]_q}. Thus,

    \displaystyle  \prod_{i=1}^{p} (1+q^i) = 2 \mod [p]_q

    Also, observe that last term in the above product : {(1+q^p)}, reduces to {2} modulo {[p]_q}. So we may further simplify the above identity to,

    \displaystyle  \ \prod_{i=1}^{p-1} (1+q^i) = 1 \mod [p]_q

    We emphasize again that this is true only for odd primes {p}.

  2. The exponents in the identity (1)

    \displaystyle  e(n,r,d) = {\lfloor n/d \rfloor - \lfloor r/d \rfloor - \lfloor (n-r)/d \rfloor }

    are all either {1} or {0} , according as the the remainder when {d} divides {r} is greater or smaller than remainder when {d} divides {n}. In particular, since {d |n \Leftrightarrow e(n,d+1,d) = 1}, it follows that,

    \displaystyle  \Phi_{d}(q) | \binom{n}{d+1}_q \Leftrightarrow \quad d|n

    Stated differently, this means that

    \displaystyle  \Phi_d(q) | \binom{n}{r}_q \text{whenever} \quad d | \text{gcd}(n,r-1)

    Using the above result, a primality condition can be given, similar to the ones involving standard binomial coefficients can be given in terms of {q}-binomials as well. A number {n} is prime if and only if:

    \displaystyle  \binom{n}{d}_q = 0 \mod [n]_q \quad \text{for all d, s.t} \quad 0<d<n

Categories: Uncategorized

ponder problem now on last legs

May 1, 2011 Leave a comment

This post culminates our efforts in solving the problem:

If {x,y} are positive integers with {y>1} and satisfying the following {x^n-1} is divisible by {y^n-1} for all positive integers {n}, then {x} is a power of {y}.

First recap a few facts from this post: We began by showing that:

\displaystyle  p(n) = (x-y)\cdot (x-y^2) \cdots (x-y^n)

is divisible by {(y^r-1)^{\lfloor n/r \rfloor}} for all {r \leq n} and therefore by the lcm,

\displaystyle  l(n) = \text{lcm} ( (y-1)^n, (y^2-1)^{ \lfloor n/2 \rfloor } , \ldots, (y^r-1)^{\lfloor n / r \rfloor }, \ldots , (y^n-1) )

We however wanted a stronger divisibility condition that {p(n)} should be divisible by,

\displaystyle  q(n) = \prod_{i=1}^n(y^i-1)

For then, the sequence,

\displaystyle  p(n)/q(n), \text{ for } n = 1,2,\ldots

consists of integers only, and if we let {g =  (x,y)}, this will in turn show that the sequence {\frac{p(n)}{g^n \cdot q(n)}} also consists of integers only. But as, {\frac{p(n)}{g^n \cdot q(n) }} converges to {0} as {n \rightarrow \infty}, this will prove that for large enough integer {r}, {p(r)} vanishes, showing that {x=y^r}. For the skeptics amongst us, here is a quick proof of the fact that {\frac{p(n)}{ g^n q(n)} \rightarrow 0} as {n \rightarrow \infty}. We recall from our analysis courses that the product of

\displaystyle  \prod_{i=1}^n(1 - (x-1)/(y^i-1))

converges absolutely iff {\sum_{i=1} (x-1)/(y^i-1)} converges absolutely, provided {1> (x-1)/(y^i-1)} for all large i. Now the result that {\frac{p(n)}{g^n \cdot q(n)} \rightarrow 0} as {n \rightarrow \infty} follows by verifying these facts and the fact that {1/g^n \rightarrow 0}.

So to wind up the proof, we need to show that {q(n) | p(n)}. Since we know that {l(n) | p(n)} we will show that {q(n) | p(n)}, by proving that each prime power dividing {q(n)/l(n)} also divides {p(n)}

The last post allowed us to write {l(n)} and {q(n)} in terms of cyclotomic polynomials:

\displaystyle  l(n) = \text{lcm}( \Phi_1(y)^n , \Phi_2(y)^{\lfloor n/2 \rfloor} , \ldots , \Phi_n(y) )

and

\displaystyle  q(n) = \prod_{r=1}^n {\Phi_r(y)^{\lfloor n/r \rfloor}}

In an earlier post we also showed that for distinct integers {1\leq i<j}, {\text{gcd} (\Phi_i(y), \Phi_j(y))} is a prime number {p} or {1}. If not {1}, it is the prime {p} only if {j=p^s\cdot i} for some {s\ge 0}. Also if {p |\Phi_{ip^m}(y)} then using the formula,

\displaystyle  \Phi_{ip^m}(y) = \Phi_{ip}(y^{p^{m-1}})

and going modulo {p}, we get

\displaystyle  0 = \Phi_{ip^m}(y) \mod p = \Phi_{ip}(y^{p^{m-1}}) \mod p = \Phi_{ip}(y) \mod p

Let {p} be a prime such that {p |\Phi_{i}(y)} and {p {\not |} \Phi_j{y}} for positive integers {j < i}. The highest power of {p} in the product,

\displaystyle  q(n) = \prod_{j=1}^n\Phi_j(y)^{ \lfloor n/j \rfloor}

is,

\displaystyle  p^{s\lfloor n/i \rfloor + \lfloor n/ip \rfloor + \lfloor n/{ip^2} \rfloor + \ldots \lfloor n/{ip^m} \rfloor } \ \ \ \ \ (1)

where {s} is the highest power on {p} dividing {\Phi_i(y)} and {m} is the largest integer ({\leq n}) such that {(\Phi_{ip^m}(y),\Phi_i(y) ) = p}. The number {m} is bounded by the integer {m'} satisfying {n/p \le ip^{m'} \le n}.

On the other hand, the highest power of the prime {p} dividing {l(n)} is {p^{s \lfloor n/i \rfloor}}. To show that {q(n) | p(n)} it is enough to show that for each such {p}, the highest prime power of {p} in {l(n)/q(n)}

\displaystyle  p^{ \lfloor n/i \rfloor + \lfloor n/ip \rfloor + \lfloor n/{ip^2} \rfloor + \ldots \lfloor n/{ip^m} \rfloor }

also divides {p(n)}.

From our first post on the problem, if {p | \Phi_{i}(y)} then {p |\prod_{j=1}^{i} (x-y^j))}. If {i} is the smallest integer for which {p | \Phi_i(y)}, there exists a unique {a_1} in {\{1\ldots i\}}, such that {x=y^{a_1} \mod p}. In fact, if {s} is largest integer such that {p^{s} | \Phi_i(y)}, then {x = y^{a_1} \mod p^{s}} by the minimality of {i}. Now consider the numbers,

\displaystyle  r(k) = \frac{(x-y^{a_1 +ki} )}{p^{s}}

where {k} is an integer such that {n \ge a_1 + ki \ge 0}. It is clear that the numbers {r(k)} are integers. Taking any {p} consecutive integer values of {k}, we get {p} distinct numbers {r(k)} no two of which are same modulo {p}, for otherwise, {p^s} would not be the largest prime power dividing {y^i-1}. Thus, there is {a_2} such that {p |r(a_2)}. There are {\lfloor n/i \rfloor} disjoint groups of consecutive terms of size {i}, in the product {\prod_{i=1}^n(x-y^i)} each giving us an additional factor of {p^{ \lfloor n/i \rfloor }} in the product. Likewise, if we consider numbers {(x-y^{a_1+a_2i+lip})/p^{s+1}} where {l} is any integer for which {n \ge a_1+a_2i + lip \ge 0}, repeating the arguments in the previous paragraph, for every {p} consecutive values of {l}, there exists {l} such that {(x-y^{a_1+a_2i+lip })/p^{h+1}} is a multiple of {p}. Since there are {\lfloor n/ip \rfloor} groups of consecutive terms of size {ip} in the product {p(n)}, giving us { p^{ \lfloor n/(ip ) \rfloor }} additional prime powers in {p(n) = \prod_{j=1}^n(x-y^j )}. We can continue this process until we get all the additional prime powers

\displaystyle  p^{\lfloor n/i \rfloor + \lfloor n/(ip ) \rfloor +\ldots + \lfloor n/(ip^m )\rfloor} )

in {p(n)}, where {m} is such that {n/p \le ip^m \le n}. This prime power is clearly divisible by the prime power of {p} in {q(n)/l(n)} in (1).

Categories: number theory

another nugget concerning cyclotomic polynomials

April 26, 2011 1 comment

In our build up to a proof of this problem., we established that the product

\displaystyle  p(n) = \prod_{i=1}^n(x-y^i)

is a multiple of each of the numbers {(y^i-1)^{\lfloor n/i \rfloor }} for {1\leq i \leq n}. But we wished to show the stronger result that {p(n)} is divisible by {q(n) = \prod_{i=1}^n(y^i-1)}. One way to proceed to estimate how the lcm,

\displaystyle  l(n) = \text{lcm}\{(y-1)^n, (y^2-1)^{\lfloor n/2 \rfloor}, \ldots, (y^r-1)^{\lfloor n/r \rfloor} , \ldots, (y^n-1) \}

differs from the product {q(n) = \prod_{i=1}^n(y^i-1)} and see if { l(n)/q(n)} also divides {p(n)}. We take the cyclotomic route, using the identity,

\displaystyle  y^n-1 = \prod_{d|n} \Phi_d(y)

to rewrite {l(n)} as,

\displaystyle  l(n) = \text{lcm} \{ \Phi_1(y)^n, \ldots, \Phi_{r}(y)^{\lfloor n /r \rfloor} , \ldots, \Phi_n(y)\}

We also write q(n) using cyclotomic polynomials as,

\displaystyle  \prod_{i=1}^n(y^i-1) = \prod_{r=1}^n {\Phi_r(y)^{\lfloor n /r \rfloor}}

To see this, we write,

\displaystyle  \Phi_r(y) = \prod_{d|r}(y^d-1)^{\mu(r/d)}

where {\mu} is the Mobius function. Then the power on {(y^d-1)} in the product,

\displaystyle  \prod_{r=1}^n (\prod_{d|r} (y^d-1)^{\mu(r/d)}) ^ { \lfloor n/r \rfloor}

is

\displaystyle  \sum_{r,d|r}^n \mu(r/d) {\lfloor n/r \rfloor } = \sum_{1\leq i \leq n}^{n/d} \mu(i) {\lfloor {n/id} \rfloor}

The later sum is of the form

\displaystyle  \sum_{1 \le i \le x} \mu(i) G(x/i)

with {x = n/d} and {G(x) = \lfloor x \rfloor = \sum_{1\leq i \leq x} 1} , reminding us, that we can use the Mobius inversion formula to obtain,

\displaystyle  \sum_{1\leq i \leq n/d}^n \mu(i) {\lfloor { n/id} \rfloor} = 1

Thus,

\displaystyle  \prod_{r=1}^n\Phi_{r}(y)^{\lfloor n/r \rfloor} = \prod_{r=1}^n (y^r-1) = q(n)

Our next task is to estimate {q(n)/l(n)} which we will do in the next post.

a result concerning cyclotomic polynomials

April 24, 2011 1 comment

In this post we record a useful result concerning cyclotomic polynomials. This will help us prove what is claimed in this post.

Theorem: For distinct positive integers {i,j} the GCD of the values of cyclotomic polynomials {\Phi_i(y)} and {\Phi_j(y)} , is {p} only if {j = i \cdot p^k} for some integer {k \ge 1}. On the other hand, if {j = i \cdot p^k} for some {k \ge 1}, {(\Phi_i(y) , \Phi_j(y)) = p \text{ or } 1}.

Proof: ({\Leftarrow}) We show that {j = i \cdot p^k} for some {k \ge 1} if {p | (\Phi_j(y), \Phi_i(y))}. We will start by proving that the gcd {g=(i,j)=i}. Then show that j/i is a prime power. Let {g = (i,j)} and assume to the contrary that {g < i}. The cyclotomic polynomials {\Phi_i(y)} and {\Phi_j(y)} divide {\frac{(y^j-1)}{(y^g-1)}} and {\frac{(y^i-1)}{(y^g-1)}} resp. But, {\frac{(y^i-1)}{(y^g-1)}} and {\frac{(y^j-1)}{(y^g-1)}} are relatively prime (easy exercise), and so their divisors {\Phi_i(y)} and {\Phi_j(y)} are also relatively prime. This shows that if for {1 \le i < j}, the values of cyclotomic polynomials {\Phi_i(y)} and {\Phi_j(y)} have a factor in common then {\text{gcd}(i,j) = i}.

Now suppose {j= m \cdot i} and that, a prime {p}, divides the values of cyclotomic polynomials {\Phi_i(y)} and {\Phi_j(y)}. But {\Phi_j(y)} divides

\displaystyle \frac{ (y^j-1)}{(y^i-1)}=1+y^i+ \ldots + y^{i(m-1)},

and so {p} also divides it. Going modulo {p}, we see that {(y^j-1)/(y^i-1) \mod p=m}. This proves that {m} is a multiple of {p}. Next we show that {m} is a power of {p}.

Let {p^h} be the largest power of {p} dividing {i} and {p^k} be the largest power of {p} that divides {j = i\cdot m}. Now using Thm 1.1 of \cite{YVES}, we have,

\displaystyle  \Phi_{i}(y) | \Phi_{i/p^h}(y^{p^h}) \text{ and } \Phi_{im} (y) | \Phi_{im/p^k} (y^{p^k})

Now, {\Phi_{i/p^h}(y^{p^h}) \mod p = \Phi_{i/p^h} (y)} and {\Phi_{im/p^k} (y^{p^k}) \mod p = \Phi_{im/p^k} (y)}. Since {p | \Phi_i(y)} and {p | \Phi_j(y)}, {p} divides both { \Phi_{im/p^k}(y)} and { \Phi_{i/p^h}(y)}. From the arguments in the first paragraph of this proof, this is possible only if {im/p^k = i/p^h} or {m = p^{k-h}}. Hence {j = i p^{k-h}}.

({\Rightarrow}) Let {j = i \cdot p^k} ({k>0}). From the proof in the “only if” direction {p} is the only prime that can possibly divide { (\Phi_i(y), \Phi_j(y))}. To show that

\displaystyle {(\Phi_i(y),\Phi_j(y) = p \text{ or } 1}

it will be enough to show that

\displaystyle {p | (\Phi_i(y) , \Phi_j(y)) }  \Rightarrow {p^2 {\not |} \Phi_j(y)}

First suppose {p^k \neq 2}. Since {p | \Phi_i(y)}, we must have, {p | (y^i-1)} and so we may write {y^i \mod p^2= 1 + ap \mod p^2}, for some {a \in \{0,\ldots, p-1\}}. Also, as {\Phi_j(y) | (y^{i p^k} -1 ) / (y^i-1)}, it is enough to show that {p^2 {\not |} (y^{i p^k} -1 ) / (y^i-1)} to show that {p^2 {\not |} \Phi_j(y)}. Consider,

\displaystyle  (y^{i p^k} -1 ) / (y^i-1) \mod p^2 = 1 + y^i + \ldots + y^{(p^k-1)i} \mod p^2

\displaystyle  = p + ap + 2 ap + 3 ap + \ldots + (p^k-1) ap \mod p^2

\displaystyle  = p + ap ( p^k ( p^k-1)/2 ) \mod p^2 = p \mod p^2

Thus {p^2 {\not |} (y^{i p^k} - 1) / (y^i-1)}. If {j = 2i} with {p=2}, and {i} is an even number then {\Phi_j(y) | (y^{2i}-1) / (y^i-1) = 1 + y^i \mod 4 \neq 0}. If {i} is odd then,

\displaystyle \Phi_{2i} (y) = \Phi_i(-y) | (y^{i} + 1)/(y+1) = 1 - y + y^2 - \ldots + y^{i-1}

. The last value modulo {4} is an odd number and so is not a multiple of {4}. Hence in any case {p^2 {\not |} (y^{j}-1)/(y^i-1)}

This shows that {p^2 {\not |}\Phi_j(y)} and that {(\Phi_j(y),\Phi_i(y) ) = p \text{ or } 1}.

{9} \bibitem{YVES} Y. Gallot, Cyclotomic polynomials and Prime Numbers, \url{http://perso.orange.fr/yves.gallot/papers/cyclotomic.pdf}

an old ponder problem

April 22, 2011 5 comments

It is well-known that if natural numbers {x>1} and {y>1} satisfy {x = y^n}, for some {n>0}, then {(x^i-1)} is a multiple of { y^i-1} for all {i>0},. April 2005 ponder asks whether the converse is true, that is if for integers { x>1,y>1}, the number { x^i-1} is a multiple of { y^i-1} for all { i > 0}, then {x} a power of { y}.

While trying to prove this I stumbled on this interesting polynomial identity:

\displaystyle  \prod_{i =1 }^n ( x - y^i) = \sum_{r=0}^n (-1)^{n-r}x^{r} y^{\frac{(n-r) (n-r+1)}{2}} C^n_{n-r}(y)

where

\displaystyle  C^n_r(y) =  \prod_{j=1}^r \frac{(y^{n-j+1}-1) }{y^j - 1}

{C^n_r(y)} looks similar to the binomial coefficient {C^n_r = \prod_{j=1}^r (n-j+1)/j}. Importantly, {C^n_r(y)} is an integer for integer values of {y>1}.

To use this identity for the problem at hand, we first note that setting {x=y} causes LHS to vanish and so we may replace each of the terms {x^r} in RHS by {(x^r-y^r)} without changing the value of the expansion. But wait, {(x^r-y^r)} is a multiple of {y^r-1} for {r>0} by hypothesis. We may pull out the denominator {y^r-1} and the numerator {y^n-1} in the RHS to rewrite this identity as:

\displaystyle  \prod_{i=1}^n ( x - y^i) = \sum_{r=1}^n {(-1)^{n-r}(x^r - y^r) \cdot \frac{(y^n-1)}{(y^r-1)} y^{\frac{(n-r) (n-r+1)}{2}} \prod_{j=1}^{r-1} \frac{(y^{n-j}-1 ) }{y^{j} - 1 }}

It is now apparent that each of the terms in the summand in RHS is a multiple of { y^n - 1} and therefore product

\displaystyle  p(n) = \prod_{i=0}^n{(x-y^i )} \text{ is a multiple of } (y^n-1)

In fact, one easily sees that,

\displaystyle  p(n) \text{ is a multiple of } (y^r-1)^{ \lfloor n/r \rfloor }

for each {r} in {1\ldots n}. If we up our optimism a bit, we are led to suspect that

\displaystyle  p(n) = \prod_{i=1}^n (x-y^i) \text{ is a multiple of } q(n) = \prod_{i=1}^n(1-y^i)

Among the factors of {p(n)} that are relatively prime to {q(n)}, one candidate is {g^n} where {g = \text{gcd}(x,y)}. But is {g>1}?. We can squeeze out this easy fact from the hypothesis: Every prime {p} that does not divide {y} also does not divide {x}. For if {p {\not |} y} then {p | y^s-1} for some {s\ge 1} and so {p | x^s-1} and therefore {p} cannot divide {x}. Stated differently, this says that every prime that divides {x} also divides {y}. Given that both {x,y} are greater than {1}, this means that {\text{gcd}(x,y) = g>1}.

It is still not clear whether {q(n) | p(n)}, but if we take this to be true how can we prove the ponder problem?. To see this, observe that

\displaystyle  r(n) = \frac{p(n)}{g^n q(n)}

approaches zero as {n \rightarrow \infty}, so if we show that each of the terms in the sequence {r(n)} is an integer, it would mean that the numerator {p(n)} of {r(n)} vanishes for some large {n}, proving that {x = y^n} for some {n\geq 1}.

Given that {g} and {q(n)} are relatively prime, we just need to show that {p(n)/q(n)} is an integer in order to show that {r(n)} is an integer. Which is what we will proceed to do in the next few posts.

Categories: Uncategorized

A problem

December 30, 2009 4 comments

Let A and B be connected subsets of [0,1]2 where π(A) = [0,1] = π(B) where π is the projection map π(x,y) = x. We construct a new set C out of A and B as follows.
Let C = {(x,y,z) | (x,y) ∈ A and (x,z) ∈ B}.

Is C connected always? If not then are there counterexamples?
Read below to see an answer.

Here is a counter example to the statement where the set C generated by A and B as in figure below, is not connected:

Now comes the interesting question. Given such sets A and B, can we always find a connected set whose projections are A and B respectively.? The answer is provided here at m.o.

Follow

Get every new post delivered to your Inbox.