## arc length

In this post we look at an algorithm to compute arc lengths of a differentiable curve. First lets recall the definitions:

Let $\mathbf{r}$ be a the curve parametrized by $t \in [0,1]$.
$\displaystyle \gamma(t) = \int_{[0,t]}\sqrt{\mathbf{r}'(t) \cdot \mathbf{r}'(t) } \,dt$

The thing that is niceĀ aboutĀ arc lengths is that they are integrals and behave well even when our curve fails to be differentiable at places. The thing that is not nice (computationally) is that for general polynomial curves this integral may not have closed form expression. Try this in wolfram alpha for example:

Integrate[Sqrt[1 + x + 2 x^2 + x^5], x]

We thus have to resort to numerical techniques, such as the Gaussian quadrature to get an answer. Gaussian quadrature is a remarkably effective tool too(esp for smooth functions) and whats more the convergence is fast for all practical purposes( error ~ $O(f^{(2n)}(\eta))$ for $n$ term evaluation where $f$ is what is being integrated). This does not mean we should stop playing with this and see where it can take us. The complexity comes from the square root right, lets get rid of it and start playing.

Lets write
$\displaystyle \Gamma(t) = \int_{[0,t]} {\mathbf{r}'(t) \cdot \mathbf{r}'(t) } \,dt$

This is a tractable problem and definitely can be evaluated for polynomial curves but it is way off the result. Lets us see the connection between the two

$\displaystyle \Gamma'(t) = (\gamma'(t))^2$

This depends purely on the derivatives and there appears no direct way to retrieve the arc length from this. Lets try to bringing in a friend of of $\gamma$ to see a better connection. Define $\displaystyle \eta(t) = \gamma(t)/\gamma'(t)$ and differentiate.

$\displaystyle \eta'(t) = 1 - \frac{\gamma(t)\gamma''(t)}{\gamma'(t)^2}$
or

$\displaystyle \eta'(t) = 1 - \eta(t)\frac{\Gamma''(t)}{2 \Gamma'(t)}$

Since we have come this far, let take this as far as it gets us. Rewrite the above with $\eta$ on lhs

$\displaystyle \eta(t)\Gamma''(t) = 2 { \Gamma'(t)} (1 - \eta'(t))$
or
$\displaystyle \eta(t)\Gamma''(t) + \eta'(t)\Gamma'(t) = 2\Gamma'(t) - \Gamma'(t) \eta'(t)$
or
$\displaystyle (\eta(t) \Gamma'(t))' = (2 - \eta'(t))\Gamma'(t)$

Note that lhs is ready for integration but rhs is not. If we can express $\eta'(t)$ (in the rhs) as a power series in terms of $\Gamma(t)$ then integrating rhs is also easily done. We can worry about the fact that power series exists later(see, we are in real world) lets follow this trail anyway.

Lets write
$\displaystyle \eta'(t) = c_0 + c_1 \Gamma(t) + c_2 {\Gamma(t)}^2 + \ldots$

then
$\displaystyle \eta(t) = c_0 t + c_1 \int \Gamma(t) dt + c_2 \int \Gamma(t)^2 dt + \ldots$

Our job is to find $c_0 , c_1,\ldots$ such that both sides match. At this point we have to break off and do a hand calculation which reveals the following (or use as CAS tool to get these identities as you prefer)

$\displaystyle c_0 = 1$
$\displaystyle c_1= -\frac{\Gamma ''(0)}{2 \Gamma '(0)^2}$
$\displaystyle c_2= \frac{7 \Gamma ''(0)^2-4 \Gamma ^{(3)}(0) \Gamma '(0)}{8 \Gamma '(0)^4}$
$\displaystyle c_3= \frac{-77 \Gamma ''(0)^3-12 \Gamma ^{(4)}(0) \Gamma '(0)^2+74 \Gamma ^{(3)}(0) \Gamma '(0) \Gamma ''(0)}{48 \Gamma '(0)^6}$
$\displaystyle c_4= \frac{1155 \Gamma ''(0)^4-32 \Gamma ^{(5)}(0) \Gamma '(0)^3+192 \Gamma ^{(3)}(0)^2 \Gamma '(0)^2+316 \Gamma ^{(4)}(0) \Gamma '(0)^2 \Gamma ''(0)-1526 \Gamma ^{(3)}(0) \Gamma '(0) \Gamma ''(0)^2}{384 \Gamma '(0)^8}$

You can see additional terms here. Calculated using

We can retrieve the arc length from this by using the identity

$\displaystyle \gamma(t) = \gamma'(t) \eta(t)$.
or

$\displaystyle \gamma(t) = \gamma'(t) (c_0 t + c_1 \int \Gamma(t) \,dt + c_2 \int \Gamma(t)^2 \,dt + \ldots )$

But wait, there is another way we can retrieve $\gamma$ without involving additional integrals:
$\displaystyle \gamma(t) = \frac{ \gamma'(t)^2 \cdot (1 - \eta'(t) )}{\gamma''(t)}$
or

$\displaystyle \gamma(t) = -{\gamma'(t)^2/\gamma''(t)} \cdot (c_1 \Gamma(t) + c_2 \Gamma(t)^2 + \ldots )$

Lets unit test this with a basic function:

$\displaystyle y = x^2/{\sqrt 2}$

parametrized by $x = t/{\sqrt 2}, y = \frac{t^2}{2{\sqrt 2}}$

The closed form of the arc length of this parabola is:
$\displaystyle (t \sqrt{1+t^2}+\sinh^{-1} {t})/(2 \sqrt{2})$
(courtesy wolfram alpha) and this has the series expansion

$\displaystyle t/\sqrt{2} + t^3/(6 \sqrt{2}) - t^5/(40 \sqrt{2}) + t^7/(112 \sqrt{2}) + \ldots$

Using our calculations we get,
$\displaystyle c_0 = 1, c_1 = 0, c_2 = - 4, c_3 = 0, c_4 = 32$ from which

$\gamma(t) = \displaystyle {\sqrt \frac{1 + t^2}{2}} (t - 4 (t^3/12 + t^5/30 + t^7/252)) + 32 ( t^5/80 + t^7/84 + O(t^9) )$

which has the power series expansion:

$t/\sqrt{2}+t^3/(6 \sqrt{2})-t^5/(40 \sqrt{2})+(3057 t^7)/(5040 \sqrt{2}) + O(t^9) )$
if one uses the expansion that does not involve integrals we get

$t/\sqrt{2}+t^3/(6 \sqrt{2})-(301 t^5)/(72 \sqrt{2})-(275 t^7)/(48 \sqrt{2})+O(t^9)$
which has error an order of magnitude larger than the previous expansion.

## Parametrization

Now, having come this far let us also look to see if we can parameterize the curve using arc length.
Given arc length s, our task is to find $t$ such that $s = \gamma(t)$
Using our series expansion, we may write

$\displaystyle t = s/\gamma'(t) - \int_{[0,t]}\sum_i c_i \Gamma_i(t)\,dt$

which suggests fixed point algorithm using $t_{j+1} = F(t_j)$ where
$\displaystyle F(t) = s/\gamma'(t) - \int_{[0,t]}\sum_i c_i \Gamma_i(t)\,dt$
this would converge provided $\left|F'(t)\right| < 1$ which would be true if
$\displaystyle |\frac{s \gamma''(t)}{\gamma'(t)^2} + \sum_i c_i\Gamma_i(t) | < 1$
or
$\displaystyle \left |s - \gamma(t)\right | < \frac{\gamma'(t)^2}{\gamma''(t)}$
The scheme will hence get us to the fixed point provided $\gamma'(t)^2$ stays away from zero and $\gamma''(t)$ is never unbounded.

Categories: Uncategorized

## Waist on a torus

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 ${) 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

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

Categories: Uncategorized

## ponder problem now on last legs

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, ${\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

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