## arc length

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

Let be a the curve parametrized by .

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 ~ for term evaluation where 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

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

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 to see a better connection. Define and differentiate.

or

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

or

or

Note that lhs is ready for integration but rhs is not. If we can express (in the rhs) as a power series in terms of 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

then

Our job is to find 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)

You can see additional terms here. Calculated using

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

.

or

But wait, there is another way we can retrieve without involving additional integrals:

or

Lets unit test this with a basic function:

parametrized by

The closed form of the arc length of this parabola is:

(courtesy wolfram alpha) and this has the series expansion

Using our calculations we get,

from which

which has the power series expansion:

if one uses the expansion that does not involve integrals we get

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 such that

Using our series expansion, we may write

which suggests fixed point algorithm using where

this would converge provided which would be true if

or

The scheme will hence get us to the fixed point provided stays away from zero and is never unbounded.

## 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 internally disjoint convex pieces of equal area and perimeter. The problem has since been proved when 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 which has the -antipodal property: , there is a pair of separators of a torus along its “waist” that map to zero under . More specifically, there is a subset of the zero set of which is such that the projection map restricted to is not null homotopic. For larger powers of , the notation gets a little unwieldy but the proof scales up well. Lets tackle notation first:

Label the coordinates of in a binary system, with words using the letters , and . The words that can be formed using these letters can be treated as vertices in a binary tree, with the word as the root node. The root node has a unique child vertex as the word . Other vertices consist of words in letters ( of length ) each having child nodes and . For example, the binary tree for would have vertices as below:

If we impose the dictionary ordering on such words, , then each word of length uniquely identifies a coordinate in . For example, a point in can be written as .

Let be the set of words representing indices to coordinates of points in that have letters in 0,1 and 2, with 0 appearing only as the starting letter and are of length not more than . For each word of length we define to be the projection map: . Given , we define a map as follows:

and for every other word , .

For instance, for and , we have,

Thus, changes the sign of the coordinate with index and swaps coordinates with indexes with , leaving all the other coordinates fixed. If represents a subword of consisting of first letters from , then using the definition of , we note in particular, that . Finally let to be the map that gives the length of a word in .

Definition 1 (-antipodal map)For , we say that a map is -antipodal, if,

.

Theorem 2Let be a continuous map with the -antipodal property for each word . Suppose there exists such that . Then the zero set of contains a connected subset which can be approximated arbitrarily closely in the Hausdorff distance by a smooth loop , for which the projection map: , is not null-homotopic.

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

Lemma 2Let be a real valued function defined on the connected closed subset on the torus such that projection defined by is not null-homotopic. Then there exists two points and in such that .

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

## q-binomials

The binomial like coefficients that we saw in earlier posts:

are called –binomial coefficients. In keeping with the existing convention we will use as the indeterminate instead of and write for

It was established in an earlier post that:

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

We also made use of the identity:

If we put in the above equation, we get

We now discuss a few consequences of the above identities:

- For any natural number , and , is divisible by . For the special case where is a prime, is divisible by ( for which we will use the shorter notation as in wikipedia). Consequently we have,
For odd primes , modulo . Thus,

Also, observe that last term in the above product : , reduces to modulo . So we may further simplify the above identity to,

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

- The exponents in the identity (1)
are all either or , according as the the remainder when divides is greater or smaller than remainder when divides . In particular, since , it follows that,

Stated differently, this means that

Using the above result, a primality condition can be given,

*similar*to the ones involving standard binomial coefficients can be given in terms of -binomials as well. A number is prime if and only if:

## ponder problem now on last legs

This post culminates our efforts in solving the problem:

If are positive integers with and satisfying the following is divisible by for all positive integers , then is a power of .

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

is divisible by for all and therefore by the lcm,

We however wanted a stronger divisibility condition that should be divisible by,

For then, the sequence,

consists of integers only, and if we let , this will in turn show that the sequence also consists of integers only. But as, converges to as , this will prove that for large enough integer , vanishes, showing that . For the skeptics amongst us, here is a quick proof of the fact that as . We recall from our analysis courses that the product of

converges absolutely iff converges absolutely, provided for all large i. Now the result that as follows by verifying these facts and the fact that .

So to wind up the proof, we need to show that . Since we know that we will show that , by proving that each prime power dividing also divides

The last post allowed us to write and in terms of cyclotomic polynomials:

and

In an earlier post we also showed that for distinct integers , is a prime number or . If not , it is the prime only if for some . Also if then using the formula,

and going modulo , we get

Let be a prime such that and for positive integers . The highest power of in the product,

where is the highest power on dividing and is the largest integer () such that . The number is bounded by the integer satisfying .

On the other hand, the highest power of the prime dividing is . To show that it is enough to show that for each such , the highest prime power of in

also divides .

From our *first post* on the problem, if then . If is the smallest integer for which , there exists a unique in , such that . In fact, if is largest integer such that , then by the minimality of . Now consider the numbers,

where is an integer such that . It is clear that the numbers are integers. Taking any consecutive integer values of , we get distinct numbers no two of which are same modulo , for otherwise, would not be the largest prime power dividing . Thus, there is such that . There are disjoint groups of consecutive terms of size , in the product each giving us an additional factor of in the product. Likewise, if we consider numbers where is any integer for which , repeating the arguments in the previous paragraph, for every consecutive values of , there exists such that is a multiple of . Since there are groups of consecutive terms of size in the product , giving us additional prime powers in . We can continue this process until we get all the additional prime powers

in , where is such that . This prime power is clearly divisible by the prime power of in in (1).

## another nugget concerning cyclotomic polynomials

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

is a multiple of each of the numbers for . But we wished to show the stronger result that is divisible by . One way to proceed to estimate how the lcm,

differs from the product and see if also divides . We take the cyclotomic route, using the identity,

to rewrite as,

We also write using cyclotomic polynomials as,

To see this, we write,

where is the Mobius function. Then the power on in the product,

is

The later sum is of the form

with and , reminding us, that we can use the Mobius inversion formula to obtain,

Thus,

Our next task is to estimate which we will do in the next post.

## a result concerning cyclotomic polynomials

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 the GCD of the values of cyclotomic polynomials and , is only if for some integer . On the other hand, if for some , .

*Proof*: () We show that for some if . We will start by proving that the gcd . Then show that is a prime power. Let and assume to the contrary that . The cyclotomic polynomials and divide and resp. But, and are relatively prime (easy exercise), and so their divisors and are also relatively prime. This shows that if for , the values of cyclotomic polynomials and have a factor in common then .

Now suppose and that, a prime , divides the values of cyclotomic polynomials and . But divides

and so also divides it. Going modulo , we see that . This proves that is a multiple of . Next we show that is a power of .

Let be the largest power of dividing and be the largest power of that divides . Now using Thm 1.1 of \cite{YVES}, we have,

Now, and . Since and , divides both and . From the arguments in the first paragraph of this proof, this is possible only if or . Hence .

() Let (). From the proof in the “only if” direction is the only prime that can possibly divide . To show that

it will be enough to show that

First suppose . Since , we must have, and so we may write , for some . Also, as , it is enough to show that to show that . Consider,

Thus . If with , and is an even number then . If is odd then,

. The last value modulo is an odd number and so is not a multiple of . Hence in any case

This shows that and that .

{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 and satisfy , for some , then is a multiple of for all ,. April 2005 ponder asks whether the converse is true, that is if for integers , the number is a multiple of for all , then a power of .

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

where

looks similar to the binomial coefficient . Importantly, is an integer for integer values of .

To use this identity for the problem at hand, we first note that setting causes LHS to vanish and so we may replace each of the terms in RHS by without changing the value of the expansion. But wait, is a multiple of for by hypothesis. We may pull out the denominator and the numerator in the RHS to rewrite this identity as:

It is now apparent that each of the terms in the summand in RHS is a multiple of and therefore product

In fact, one easily sees that,

for each in . If we up our optimism a bit, we are led to suspect that

Among the factors of that are relatively prime to , one candidate is where . But is ?. We can squeeze out this easy fact from the hypothesis: Every prime that does not divide also does not divide . For if then for some and so and therefore cannot divide . Stated differently, this says that every prime that divides also divides . Given that both are greater than , this means that .

It is still not clear whether , but if we take this to be true how can we prove the ponder problem?. To see this, observe that

approaches zero as , so if we show that each of the terms in the sequence is an integer, it would mean that the numerator of vanishes for some large , proving that for some .

Given that and are relatively prime, we just need to show that is an integer in order to show that is an integer. Which is what we will proceed to do in the next few posts.