Bedtime mathematics

Waist on a torus

November 22, 2011 mymbl 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 mymbl 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:

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}$ .
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 mymbl 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 mymbl 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}$

$\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.

Categories: number theory, Uncategorized

a result concerning cyclotomic polynomials

April 24, 2011 mymbl 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}

Categories: number theory, Uncategorized Tags: cyclotomic polynomials

an old ponder problem

April 22, 2011 mymbl 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 mymbl 4 comments

Let A and B be connected subsets of [0,1]² 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.

Categories: Uncategorized Tags: gt.geometric-topology

Older Entries

Bedtime mathematics

Waist on a torus

q-binomials

ponder problem now on last legs

another nugget concerning cyclotomic polynomials

a result concerning cyclotomic polynomials

an old ponder problem

A problem

Tags

Blogroll

Archives

Follow “Bedtime mathematics”