Bedtime mathematics

Waist on a torus

November 22, 2011 mymbl Leave a comment

Last year I worked on a interesting problem of 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

matrix commutators

December 26, 2009 mymbl Leave a comment

We know that set of commutators of ${n\times n}$ matrices is exactly the space of matrices of trace zero and has dimension ${n^2-1}$ . I discuss an interesting question related to this which was brought to my notice by Anamika:

Given a matrix ${C}$ of trace zero can we construct two matrices ${A}$ and ${B}$ of determinant ${1}$ , such that ${AB - BA = C}$ . Here is a proposed way of finding matrices ${A}$ and ${B}$ such that ${AB - BA = C}$ .

It turns out that this problem has a variety of applications and it goes by the name Sylvester equation (after fixing one matrix say A). For example, it is used in Computer Vision to estimate the pose(position, orientation ) of an object based on a series of images. See video here

We first try a simple case: Suppose ${D}$ is matrix with non-zero entries only in the diagonal and at locations ${i,(i+1)}$ for ${i=1,2,\ldots, n-1}$ (like in the Jordan Normal form) with ${[D]_{i\overline{i+1}} = 1}$ or ${0}$ . We want to find a matrix ${X}$ such that ${DX - XD = C}$ where ${C}$ is a ${n\times n}$ matrix with trace zero. We equate the ${i,j}$ entries on both sides to get,

$\displaystyle [C]_{ij} = \sum_{k=1}^n ( [D]_{ik} [X]_{kj} - [X]_{ik} [D]_{kj})$

expanding we get

$\displaystyle [C]_{ij} = [D]_{ii} [X]_{ij} - [X]_{ij} [D]_{jj} + [D]_{i \overline{i+1}}[X]_{\overline{i+1}j} - [X]_{i\overline{j-1}}[D]_{\overline{j-1}j}$

Now if ${\text{vec}(X)}$ denotes the operator that flattens the rectangular(column-wise) matrix to a column vector then we need to solve the system.

$\displaystyle \breve{A} \cdot \text{vec}(X) = \text{vec}(C)$

where,

We can solve the system ${\breve{A}\,\text{vec}(X) = \text{vec}(C)}$ provided ${\breve{A}}$ has maximum rank. We can reconstruct ${X}$ from ${\text{vec}(X)}$ but this does not ensure that the matrix ${X}$ is of determinant ${1}$ . We can ensure that ${X}$ has determinant ${1}$ by addition of a suitable scalar times identity matrix ( which must also be a solution trivially)

Wikipedia mentions that there is a better way to represent this matrix using tensor product ${\otimes}$ ( also called Kronecker product of matrices http://en.wikipedia.org/wiki/Kronecker_product):

$\displaystyle \breve{A} = I_n \otimes A - A^T \otimes I_n$

where ${I_n}$ is the ${n\times n}$ identity matrix.

0.1. Related results

On a related note, here is another question. Can you produce matrices ${E}$ and ${F}$ such that the commutator ${EF - FE}$ is the sum of two other ${n \times n}$ commutators ${AB-BA}$ and ${CD-DC}$ ? . Using the methods above we can find ${E}$ and ${F}$ indirectly, but is there a simple representation of ${E}$ and ${F}$ in terms of ${A,B,C,D}$ ? I do not know. However here are some insights:

Suppose ${e_{ij}}$ denotes the matrix with ${1}$ only at the position ${i,j}$ , ( ${1\leq i,j \leq n}$ ), in the matrix and the rest filled by zeros. We use the fact that the set of ${n\times n}$ matrices which are commutators is a linear space with basis:

$\displaystyle e_{ij} = e_{ii}e_{ij} - e_{ij}e_{ji} \text{ for } i \neq j$

and

$\displaystyle e_{ii} - e_{i+1\,i+1}$

I will leave this to the diligent reader to see why this is true. This says that any ${n\times n}$ commutator ${CD - DC}$ is a linear combination of these basis vectors. Armed with this result we can break the original problem down to the following two problems:

Given matrices ${n\times n}$ matrices ${A,B}$ with commutator ${AB-BA}$ , the commutator ${e_{ij}}$ ( ${j \neq i}$ ) and a scalar ${c}$ , find ${E}$ and ${F}$ such that
$\displaystyle AB - BA + c (e_{ij}) = EF -FE$

.
Similarly given a scalar ${c}$ , and matrices ${A,B}$ , for each ${i}$ , find matrices ${E,F}$ such that
$\displaystyle AB - BA + c( e_{ii} - e_{i+1\,i+1}) = EF - FE$

I could not give a simple representation of ${E,F}$ in terms of ${A,B,e_{ij}}$ . For for some special cases, it seems possible. Suppose you know that for the index ${j}$ , ${B_j}$ is the only column of ${B}$ containing non-zero entries. Now choose constants ${c_k = \text{signum } b_{kj}}$ , ${k=1,2\ldots,n}$ , such that ${\sum_k c_k b_{kj} \neq 0}$ .

We next note the identity ${e_{ij} = e_{ik}e_{kj} - e_{kj}e_{ij}}$ , for ${i \neq j}$ and ${1\leq k\leq n}$ , using which we can write:

$\displaystyle (\sum_k |b_{kj}|) e_{ij} = \sum_k (c_k e_{ik}) (b_{kj} e_{kj}) - {b_{kj}e_{kj}}c_{k}e_{ik}$

where ${B_{kj}}$ denotes the entry at the location ${k,j}$ in the matrix ${B}$ . Now let ${B_j = \sum_k B_{kj}e_{kj}}$ . Next using the fact that ${e_{ik}e_{lj} = 0}$ is ${k \neq l}$ , we have ${e_{ik} B_{kj}e_{kj} = e_{ij}B_j}$ and ${B_j e_{ik} = 0 = \sum_k B_{kj}e_{kj}}$ , so the above expression for ${e_{ij}}$ can be rewritten as:

$\displaystyle (\sum_k |b_{kj}| ) e_{ij} = \sum_k{ c_k e_{ik} B_j - B_j c_k e_{ik}}$

or,

$\displaystyle e_{ij} = H_iB_j - B_jH_i$

where ${H_i = (\sum_k c_k e_{ik})/(\sum_k |b_{kj}|) }$ . Now if ${B_j = B}$ , then

$\displaystyle e_{ij} = ( H_i B - B H_i )$

Thus,

$\displaystyle AB - BA + e_{ij} = AB - BA + ( H_i B - B H_i ) = (A + H_i) B - B ( A + H_i)$

Here are other examples: For ${i\neq j}$ , ${i \neq l}$ , ${l \neq k}$ ,

$\displaystyle c e_{ij} + d e_{kl} = (c e_{ii} + d e_{kk} ) ( e_{ij} + e_{kl} ) - ( e_{ij} + e_{kl} ) ( c e_{ii} + de_{kk} )$

Also, for the case where ${ i \neq j}$ and ${k \neq i}$ , we have:

$\displaystyle c e_{ij} + de_{ki} = ( c e_{ii} + (d+c) e_{kk}) ( e_{ij} + e_{ki} ) - (e_{ij} + e_{ki} ) ( c e_{ii} + (d+c) e_{kk} )$

Categories: Uncategorized Tags: linear algebra

Three non-idiotic guesses

December 23, 2009 mymbl Leave a comment

Three problems to ponder for the next 100 years:

First one may seem contrived but thinking about this would hightlight some major properties of primes. So here it is : The number 82 is the largest positive number that cannot be written as sum of two square free numbers each having odd number of prime factors.
Motivation for this guess comes from the result of the following python program that was run on sage to compute the number of such pairs of numbers summing upto a given number.

def sqfreesum(n):
sum = 0;
for i in range(1,n ):
sum +=moebius(i)^2* moebius(n-i)^2
*( ( 1 + moebius(i))*( 1 + moebius(n-i) )/4 );
return sum;

The graph which shows the number of ways of writing a number as a sum of two such square free numbers, reveals a trend:it increasingly stays away from zero. In fact after taking off from 82, where it is zero, it never seems to drop down.

Note that we can always write a number as a sum of two square free numbers. The numbers of ways of writing them is:
$a(n) \sim n \cdot \Pi_{p \text{ prime}} (1-2/p^2) * \Pi_{p^2|n} \frac{(p^2-1)}{(p^2-2)}$ . Have to warn you that I have not seen an actual proof but I have seen it mentioned here:
A098235
The second one is in the same spirit as the previous one. Any even number > 10 can be written as the sum of two square free numbers with one having odd number of prime factors and the other having even number of prime factors.
Motivation for this guess comes from the the result of the following python program that was run on sage to compute the number of such pairs of numbers summing upto a given number.

def sqfreesum(n):
sum = 0;
for i in range(1,n ):
sum +=moebius(i)^2* moebius(n-i)^2
*( ( 1 + moebius(i))*( 1 – moebius(n-i) )/4 + ( 1 – moebius(i))*( 1 + moebius(n-i) )/4);
return sum;

As with the previous conjecture the graph which shows the number of ways of writing a number as sum of such square free numbers. has only a few hiccups taking off, and at n=10 it achieves escape velocity. I should also mention here that any even number according to Chen Jigrun can be written as the sum of prime and semi-prime(product of two primes) or a sum of two primes. So when diluted, this result that says if Goldbach conjecture were false, we atleast know that every even positive number can be written as sum of two square free positive numbers one with odd number of prime factors( infact 1) and the other with even number of factors ( in fact 2).
Treat the following with caution please. If $\phi$ denotes the Euler totient function, then the following number is always greater than 2n.
$\sum_{i=2}^{2n-2} (2n)^{ (2n - (2n-i)\cdot i + \phi(2n-i)\cdot \phi(i)) }$ .
Proving this will prove the Goldbach conjecture. This is because, it is only when both i and 2n-i are prime that: $(2n - (2n-i)\cdot i + \phi(2n-i)\cdot \phi(i))$ is 1. There are better ways to reformulate the Golbach conjecture. One other way is the following:
Given an even number $2n$, there exists a number $k<2n$ such that
$k^2 - n^2 - \phi(k^2-n^2) = (2 n-1)$

Categories: Uncategorized Tags: number theory;

A bound for matrix norm

November 16, 2009 mymbl Leave a comment

We wish to better the bounds for the norm of a matrix ${M = (k(i,j))}$ with scalar entries when it defines a linear map with from ${l^p}$ to ${l^p}$ , that is the series ,

$\displaystyle Mx(i) = \sum_{j=1}^\infty k_{i,j} x(j)$

is convergent for each ${i}$ and ${Mx \in l^p}$ . The standard bounds for matrix norm given in the text for ${p \geq 2}$ , are ${\alpha_1^{1/p} \alpha_\infty^{1/q}}$ and ${\beta_p}$ , for ${l^p}$ spaces. We give yet another bound using the power mean inequality:

1. Power Mean Inequality :

Consider positive weights ${p_k}$ , ${k = 1, 2, \ldots, }$ which have total mass ${p_1 + p_2 + \ldots= 1}$ , then for nonnegative real numbers ${x_k}$ , ${k = 1, 2,\ldots }$ and for all ${-\infty < s < t < \infty}$ one has

$\displaystyle (\sum_{k=1}^\infty p_k x_k^s)^{1/s} \leq (\sum_{k=1}^\infty p_k x_k^t)^{1/t} \ \ \ \ \ (1)$

2. Bound for matrix norm

Consider,

$\displaystyle \begin{array}{rcl} \left | \left | Mx \right | \right |_p^p &= \sum_{i=1}^\infty \left|\sum_{j = 1}^\infty k_{i,j} x(j) \right |^p \\ &\leq \sum_{i=1}^\infty \left( \sum_{j=1}^\infty \left |k_{i,j} x(j) \right | \right )^p \\ &= \sum_{i=1,r_i \neq 0}^\infty r_i^p \left ( \sum_{j=1}^\infty \left |\frac{k_{i,j}}{r_i} x(j) \right | \right )^p \end{array}$

where for some fixed ${s > 0}$ and ${s <= 1}$ , ${r_i = \sum_{j=1}^\infty |k_{i,j}^{s}|}$ .

$\displaystyle \begin{array}{rcl} \left | \left | Mx \right | \right |_p^p & \leq \sum_{i=1, r_i \neq 0}^\infty r_i^p \left ( \sum_{j=1}^\infty \frac{\left |k_{i,j}^{s} \right |}{r_i} \left|k_{i,j}\right|^{1-s}\left| x(j) \right | \right )^p \end{array}$

Now we use power mean inequality with ${\alpha=1}$ { and } ${\beta = p}$ , ${ p_k = \frac{|k_{i,j}^{s}|}{r_i}}$ { and } ${x_k = | k_{i,j}^{1-s} x(j)|}$ . So,

$\displaystyle \begin{array}{rcl} \left | \left | Mx \right | \right |_p^p &\leq \sum_{i=1,r_i\neq 0}^\infty r_i^p \sum_{j=1}^\infty \left | \frac{|k_{i,j}^{s}|}{r_i} k_{i,j}^{p(1-s)}x(j)^p \right | \\ &= \sum_{i=1}^\infty\sum_{j=1}^\infty r_i^{p-1}\left | { k_{i,j}^{s+p(1-s)}} \right | \left|x(j)\right|^p \\ & = \sum_{j=1}^\infty \left|x(j)\right|^p \sum_{i=1}^\infty r_i^{p-1}\left | { k_{i,j}^{s+p(1-s)}} \right | \\ \end{array}$

Now if we take,

$\displaystyle \gamma_s = \sup_j \left \{ \sum_{i=1}^\infty r_i^{p-1} \left| k_{i,j}^{s + p(1-s)}\right| \right \}^{1/p}$

Then we have ${Mx \leq \gamma_s \left| \left | x \right |\right |_p}$ . So we have infinite number of bounds for the norm as we vary ${s}$ among positive reals (of course, not all values of ${s}$ might be useful )

Example : Consider the matrix

$\displaystyle A = \begin{pmatrix} 1 & 1/2^{3} & 1/3^3 & \ldots \\ 1/2 & 1 & 0 & \ldots \\ 1/3 & 0 & 1 & \ldots \\ \vdots & & & \vdots \\ \end{pmatrix}$

For this matrix ${\alpha_1 = \infty}$ and ${\beta_2}$ is also infinity, however ${\gamma}$ is finite with ${s =1/2}$ . This is because ${\sup_i r_i = \sum_n (1/n^3)^{1/2} < \infty }$ and ${\sup_{i} \sum_{j=1}^n k_{i,j}^{(2+1)/2} =\sum_{j=1}^n 1/n^{3/2} < \infty}$ . Thus ${\gamma_{2} \leq \sup_i r_i \sup_i \sum_{j=1}^n k_{i,j}^{3/2} < \infty}$ .

You can further see that ${\gamma_s}$ is a better bound than ${\alpha_\infty^{1/q}\alpha_1^{1/p}}$ always, since if we take ${s = 1}$ and ${r = \infty}$ , we have

$\displaystyle \sup_j \sum_{i=1}^\infty r_i^{p-1} \left|k_{i,j}^{s + p(1-s)}\right| = \sup_i {r_i^{p/q}} \sup_j \sum_{i=1}^\infty \left |k_{i,j}\right| \leq \alpha_\infty^{p/q} \alpha_1,$

where we have used the fact that ${p-1 = p/q}$ .

Categories: Uncategorized Tags: functional-analysis, matrix, norm

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

matrix commutators

Three non-idiotic guesses

A bound for matrix norm

Tags

Blogroll

Archives

Follow “Bedtime mathematics”