Real roots and interlacing

by HroK, Jul 22, 2012, 6:44 AM

The intermediate value theorem and Rolle's theorem are ubiquitous principles in the analysis of real roots of continuous and differentiable functions, respectively.

As the reader is likely familiar with the most standard uses of these theorems, we briefly discuss the phenomenon of interlacing functions $f,g$ with alternating real roots. (For a much more unified coverage, see Steve Fisk's paper "Polynomials, roots, and interlacing".) In particular, we look at polynomial recurrences, which provide some of the most natural examples of interlacing.

Example: The $n^{th}$ Hermite polynomial
\[H_n(x)=(-1)^n e^{x^2}\frac{d^n}{dx^n}e^{-x^2}\]has all real roots (by induction one easily verifies that $H_n$ is a polynomial of degree $n$).

Solution: We induct to show that for every $n\ge1$, $h_n(x) = \frac{d^n}{dx^n}e^{-x^2}$ has exactly $n$ roots, where the base case is obvious. But if for some $n>1$ we assume that $h_{n-1}(x)$ has $n-1$ real roots $a_1<\cdots<a_{n-1}$, then noting that $\pm\infty$ are also roots and $h_n=\frac{d}{dx}h_{n-1}$, we're done by Rolle's theorem. Obseve that $h_n,h_{n-1}$ interlace, i.e. the roots of $h_{n-1}$ lie in between those of $h_n$.$\blacksquare$

Of course, there are several variations on the same idea. For example, if we have a recurrence like $p_n(x)=xp_{n-1}(x)+p_{n-2}(x)$ and we know that $p_{n-1},p_{n-2}$ interlace, then under some mild conditions we can show via the IVT that $p_n,p_{n-1}$ and $p_n,p_{n-2}$ also interlace (of course, we need $p_n,p_{n-1},p_{n-2}$ to have degrees within one of each other). This is in essence the idea behind, for instance, Sturm's theorem.

Now for some problems, (very) roughly arranged in difficulty order!

1. (Steve Fisk) Suppose $\{a_i\},\{b_i\},\{c_i\}$ are sequences of reals where all $a_i,c_i$ are positive and the $b_i$ are unrestricted. Define a sequence of polynomials recursively by $p_{-1}=0$, $p_0=1$, and $p_i=(a_i x+b_i)p_{i-1} - c_i p_{i-2}$ for $i>1$. Show that $p_n(x)$ has all real roots for every positive integer $n$.

2. Prove Sturm's theorem.

3. (ELMO Shortlist 2012) Prove that any polynomial of the form $1+a_nx^n + a_{n+1}x^{n+1} + \cdots + a_kx^k$ ($k\ge n$) has at least $n-2$ non-real roots (counting multiplicity), where the $a_i$ ($n\le i\le k$) are real and $a_k\ne 0$.

4. Prove Newton's inequalities.
Hint

5. (Descartes' rule of signs) For a polynomial $p\in\mathbb{R}[x]$, let $z(p)$ denote the number of positive zeros and $v(p)$ the number of sign changes.

a) Show that $2\mid z(p)-v(p)$.

b) Prove that $z(p)\le v(p)$ by writing $p=(x-r)q$ for some positive real root $r$ of $p(x)$ and inducting on $\deg{p}$.

c) Prove that $z(p)\le v(p)$ by considering the derivative $p'(x)$ (assuming WLOG that $p(0)\ne0$) and inducting on $\deg{p}$.

6. (Classical) Show that out of all monic polynomials of a fixed degree $n$, $T_n(x)/2^{n-1}$ attains the smallest maximum absolute value on the interval $[-1,1]$, where $T_n(x)$ denotes the $n^{th}$ Chebyshev polynomial of the first kind.

7. (MOP 1999) Given $n$ points on the unit circle such that the product of the distances from any point on the circle to the given points does not exceed 2, prove that the points must be vertices of a regular $n$-gon.

8. (MOP 2001) Let $P(x)$ be a real-valued polynomial with $P(n) = P(0)$. Show that there exist at least $n$ distinct (unordered) pairs of distinct real numbers $\{x, y\}$ such that $x-y\in\mathbb{Z}$ and $P(x) = P(y)$. Does this necessarily hold if we allow $P$ to be any continuous function?

9. (USAMO 2002) Prove that any monic polynomial of degree $n$ with real coefficients is the average of two monic polynomials of degree $n$ with $n$ real roots.

10. (MOP 2007) Let $a$ be a real number. Prove that every nonreal root of $f(x)=x^{2n}+ax^{2n-1}+\cdots+ax+1$ lies on the unit circle and $f$ has at most 2 real roots.

11. (ELMO Shortlist 2011) If $a+b+c=a^n+b^n+c^n=0$ for some positive integer $n$ and complex $a,b,c$, show that two of $a,b,c$ have the same magnitude.
Hint

12. ("Enzo", MathOverflow) For $n\ge1$, let
\[P_n(x)=x^{n+1}\left[\frac{\partial^{2n+1}}{\partial z^{2n+1}}\frac{\sinh(z)}{\cosh(z)-1+x}\right]_{z=0}.\]Prove that $P_n(x)$ is a polynomial of degree $n$ with every root real and strictly greater than 2.
Hint
This post has been edited 11 times. Last edited by HroK, Jun 2, 2014, 8:52 AM

Binomial type identities

by HroK, Oct 1, 2011, 10:02 PM

A polynomial sequence $p_n(x)$ ($n\ge 0$) is of binomial type iff
\[p_n(x+y) = \sum_{k=0}^{n} \binom{n}{k} p_k(x) p_{n-k}(y)\]for all $x,y\in\mathbb{C}$ (e.g. $p_n(x) = x^n$ gives the binomial theorem).

First note that $p_0(x+y)=p_0(x)p_0(y)$ for all $x,y$, so if $p_0(x)$ is zero somewhere then it's zero everywhere. But then $p_n(x)=0$ trivially everywhere, so now suppose that $p_0(x)$ has no zeros, i.e. for all $x$, $p_0(x)=c$ for some constant $c\ne 0$. Then $c=c^2\implies c=1$.

To fully characterize such sequences, we work with exponential generating functions (in $\mathbb{C}[x][[t]]$). Let
\[A(x,t) = \sum_{n\ge0}\frac{p_n(x)}{n!}t^n,\]so $A(x+y,t)=A(x,t)A(y,t)$ for all $x,y\in\mathbb{C}$. Because $[t^0]A(x,t)=1$, we can formally take logarithms to get
\[\log A(x+y,t) = \log A(x,t) + \log A(y,t).\]In accordance with basic intuition, we show that there exists a formal power series
\[f(t)=\sum_{n\ge1}\frac{a_n}{n!}t^n\]such that $xf(t) = \log A(x,t)$. Indeed, if for some fixed $k$ we compare coefficients $[t^k]$ (after formally developing $\log(1+[A(x,t)-1])$, etc.), we get a polynomial identity of the form $Q_k(x)+Q_k(y)=Q_k(x+y)$, which is only satisfied by purely linear $Q_k$.

This already gives us a complete characterization based on the generating function of $p_n(x,y)$, but we can go one step further. Since $f(0)=0$, we can exponentiate both sides to get
\[\begin{align*}
\sum_{n\ge0}\frac{p_n(x)}{n!}t^n = A(x,t)
&= \exp\left(\sum_{n\ge 1}\frac{xa_n}{n!}t^n\right) \\
&= \sum_{m\ge 0}\frac{1}{m!}\left(\sum_{n\ge 1}\frac{xa_n}{n!}t^n\right)^m.
\end{align*}\]
Now equating coefficients by the multinomial formula, we have $p_n(0) = 1$ and for $n\ge1$,
\[p_n(x) = \sum_{k=1}^{n} B_{n,k}(a_1,\ldots,a_{n-k+1})x^k\]where
\[B_{n,k}(a_1,\ldots,a_{n-k+1}) = \sum_{\substack{j_1+j_2+\cdots+j_{n-k+1} = k, \\ j_1+2j_2+\cdots+(n-k+1)j_{n-k+1} = n}}\frac{n!}{j_1!j_2!\cdots j_{n-k+1}!}\prod_{i=1}^{n-k+1}\left(\frac{a_i}{i!}\right)^{j_i}.
\]is a Bell polynomial. Note that for all $n\ge 1$,
\[p_n'(0) = B_{n,1}(a_1,\ldots,a_n) = a_n.\]
Now here are some problems:

1. Verify that $x^n$, the lower factorials $x(x-1)\cdots(x-n+1)$, the upper factorials $x(x+1)\cdots(x+n-1)$, the Abel polynomials $x(x-cn)^{n-1}$, and the Touchard polynomials $\sum_{k=1}^{n}{n\brace k}x^k$ (where ${n\brace k}$ denotes a Stirling number of the second kind) are all of binomial type.

2. Prove that
\[(x+y)(x+y-cn)^{n-1} = \sum_{k=0}^{n}\binom{n}{k}xy(x-ck)^{k-1}[y-c(n-k)]^{n-k-1}\]for all reals $x,y,c$ and nonnegative integers $n$.

3. (Abel's binomial theorem) Prove that
\[(x+y)^n = x\sum_{k=0}^{n}\binom{n}{k}(x-ck)^{k-1}(y+ck)^{n-k}\]for all reals $x,y,c$ and nonnegative integers $n$.

4. (Touchard's congruence) Prove that $B_{p+k} \equiv B_{k}+B_{k+1}\pmod{p}$ where $p$ is a prime number and $B_k$ is a Bell number.

5. (Peter Ungar, AMM E 3052) Prove that
\[\sum_{k=1}^{n}\frac{(-1)^{k-1}}{k}\binom{n}{k}(n-k)^n = n^n\sum_{k=2}^{n}\frac{1}{k}\]for every positive integer $n$.

6. (AMM E 2828) Let $n$ be a nonnegative integer. Show that
\[\sum_{k=0}^{n}\binom{n}{k}(k+1)^{k-1}(n-k+1)^{n-k-1} = 2(n+2)^{n-1}.\]

7. (ISL 2009) Let $k$ be a positive integer. Show that if there exists a consequence $a_0,a_1,\ldots$ of integers satisfying the condition
\[a_n=\frac{a_{n-1}+n^k}{n},\]for all $n\ge1$ then $k-2$ is divisible by $3$.

8. (Nicholas Charles Alexander) Show that there are at most two positive integers $k$ satisfying the conditions of the previous problem.
This post has been edited 11 times. Last edited by HroK, Feb 4, 2013, 4:46 PM

Analyzing the Answer Form

by HroK, Jul 31, 2011, 5:25 AM

I think I first saw a variant of this technique when I was reading over past Polymath projects on http://gowers.wordpress.com/ where it was mentioned that methods of a certain kind wouldn't work because those types of methods typically gave sqrt(n) bounds, while there was an example for the problem that was O(ln(n)).

This is more of a general technique for problems where you want to prove some sort of bound than a specific set of theorems that can be applied.

One thing that is helpful is what is known as the Master Theorem in computer science. (http://en.wikipedia.org/wiki/Master_theorem)

As this theorem has details that would be somewhat annoying to discuss here and would make this post less accessible, if you want to learn about the Master Theorem google it and look at the wikipedia link above. However, one specific case of it is very important for olympiads: The recurrence $\text{f(n)} = 2\text{f}(\frac{\text{n}}{2}) + n$ and one of it's solutions, $\text{f(n)} = \text{n}\ln{\text{n}}.$

Here's an example of when the recurrence appears: Mergesort from computer science. The idea is basically that if you want to sort an array, you can split it into two parts A and B, sort each, and then compare the biggest from each parts to get the biggest. If the biggest is from A, compare the second biggest from A and the biggest from B to see which is the second biggest overall. And so on. How many steps does this take? It turns out to give a recurrence similar to this one. This description was not very good; if you want to read a proper treatment of Mergesort, there are several sources online, such as http://en.wikipedia.org/wiki/Mergesort.

Important note: Changing the 2 to a 3 or the $\frac{n}{2}$ to a $\frac{n}{3}$ will change the result. However, if you turn n into a multiply of n, the result will pretty much stay the same, except for a few more details. Either way, just check that your bound works for the recurrence.

So, why exactly is this recurrence so important? Because it gives one of the few ways $n\ln{n}$ is typically gotten in contest math, and maybe 90% of problems involving $n\ln{n}$ (Or $n\ln{n}$ in disguise; $n2^n$ can also be written $2^n\log_2{2^n}.$) This recurrence means that if you can find any possible way to split a problem with such a bound into 2 parts and work with each part, you can probably solve it.

On a slight tangent, induction is one of those things that I feel that people often overuse by looking at a problem and just being like "induct!" because it involves integers. I feel that induction is a technique that should mainly be used when you can find some sort of structure that allows induction to get at least some partial results, rather than a technique where you decide to induct the problem then look for something that could help the induction do something. However, I consider a bound of the form $n\ln{n}$ a strong enough sign to mean that induction will probably work.

This is all theory though, so here is a concrete example!

Warning: In my experience, full solutions are really unhelpful for actually learning how to solve problems, while quick outlines of solutions + motivation is much more helpful, so that's what I'll give. Try to fill in the details.

Let $n \geq 1$ be an integer, and let $S$ be a set of integer pairs $(a,b)$ with $1 \leq a < b \leq 2^n$. Assume $|S| > n \cdot 2^{n+1}$. Prove that there exists four integers $a < b < c < d$ such that $S$ contains all three pairs $(a,c)$, $(b,d)$ and $(a,d)$. (USA TST 2011 #8)

Quick observations:

1. Any problem with integer pairs can be interpreted as points in the coordinate plane. For this problem, this is a good idea, because you see that you get a sort of "staircase" shape.

2. The bound is $n2^n.$ (Well, technically its twice that, but for some reason you only need this. The official solution was rather silly.)

As already discussed, bounds like such tell you to induct. Staircases also tell you to induct. So, we induct. (Why do staircases tell you to induct? Well, i'll draw a picture to illustrate why, which will be included at the end of this post. Excuse my poor drawing skills. The idea is that a staircase can be split into two smaller staircases and a square.)

So basically, if we want to get the induction, we want to get a recurrence of this form. What the problem ends up reducing to is we can color at most $2n-1$ black squares in a $n$x$n$ square without getting a right triangle in which the vertex opposite the hypotenuse is the vertex that is the highest and most to the left. To prove this we notice that if we take the leftmost black square in the top row (or the first row that has black squares) then either there are no vertices to its right or no vertices below it. (And in the same row/column.) There are also no vertices left of it or above it because of how its defined, so we can either the row or the column its in only has one vertex.

And we remove the row or column and now have.... a $n$x$n-1$ rectangle that we want to prove has at most $2n-2$ black squares. When you see this, the response should be "oh... so lets generalize this problem to rectangles! And indeed, generalizing the problem to a $a$x$b$ rectangle has at most $a+b-1$ black squares solves it. (Yay.)

While this post focused on a specific answer form, in general, you want to figure out what sort of problems give what sort of answers.

Final Note: When you aren't given the answer, try to guess it from the first few values.

And now, some exercises. (In approximate order of difficulty in each section. Sections not ordered in difficulty.)

Section 1: Verifications.

1. Verify that $f(n) = n\ln{n}$ does indeed satisfy the recurrence $f(n) = 2f(\frac{n}{2})+n.$

2. Find the number of steps that mergesort takes (If you can't, try to estimate it.)

3. Complete the proof of USA TST #8.

Section 2: The meaning of various answers.

1. (Classical) Prove there are $2^n$ subsets are there of {1,2,...,$n$}?

Hint

2. (Classical) Prove that the number of permutations of {1,2,...,n} is n!.

Hint

3. (IMO 2011 #4) Let $n > 0$ be an integer. We are given a balance and $n$ weights of weight $2^0, 2^1, \cdots, 2^{n-1}$. We are to place each of the $n$ weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.
Determine the number of ways in which this can be done.

Hint

4. (USA TST 2011 #5) Let $c_n$ be a sequence which is defined recursively as follows: $c_0 = 1$, $c_{2n+1} = c_n$ for $n \geq 0$, and $c_{2n} = c_n + c_{n-2^e}$ for $n > 0$ where $e$ is the maximal nonnegative integer such that $2^e$ divides $n$. Prove that
\[\sum_{i=0}^{2^n-1} c_i = \frac{1}{n+2} {2n+2 \choose n+1}.\]

Hint

5. (Chinese quizzes 2011) Let $S$ be a set of $n$ points in the plane such that no four points are collinear. Let $\{d_1,d_2,\cdots ,d_k\}$ be the set of distances between pairs of distinct points in $S$, and let $m_i$ be the multiplicity of $d_i$, i.e. the number of unordered pairs $\{P,Q\}\subseteq S$ with $|PQ|=d_i$. Prove that $\sum_{i=1}^k m_i^2\leq n^3-n^2$.

Hint1

Hint2

6. (Source unknown.) Find the number of sequences $a_1,a_2, \ldots a_n$ such that each $a_i$ is a positive integer and if $k$ is a positive integer, then the first occurrence of $k+1$ in the sequence comes before the last occurrence of $k.$

Hint

Section 3: Rare uses of answer forms.

1. (David Yang, ELMO Shortlist 2011) Prove that we can split any graph with $n > 2$ vertices into a forest and $k$ disjoint cycles, where $k < cn\ln{n}$ for some constant c independent of n.

2. Do Section 2, Problem 3 but....

Only view if you solved the problem
Attachments:

Coloring/Weighting Invariants

by HroK, Aug 12, 2010, 4:06 AM

Hello.

I will now discuss how problems can be solved by means of coloring and weighting.

Often, a combinatorics problem will involve partitioning some set into smaller sets with a certain property. In these cases, coloring or weighting each element of the set can give valuable information about the partition.

This can be especially helpful in proving that it is not possible to obtain some tiling. Here is a tiling problem that can be solved using a standard type of coloring:

Example: Let $n, a, b$ be positive integers such that it is possible to tile an $a \times b$ rectangle using $1 \times n$ rectangles (rotations allowed). Prove that $n | a$ or $n | b$.

Solution: We place a grid on the $a \times b$ rectangle with unit squares at coordinates $(x, y)$ where $x,y$ are integers with $0 \leq x \leq a - 1$ and $0 \leq y \leq b - 1$. We color the square with coordinates $(x,y)$ with the residue class of $x + y \mod n$.

Then, it is easy to see that each $1 \times n$ rectangle contains one square of each of the $n$ colors we are using. Therefore, since we have tiled the $a \times b$ rectangle with our $1 \times n$ rectangles, each of the $n$ colors is used by the same number of squares. It is a matter of simple computation to show that this implies the result.

Coloring and weighting can also be used to construct invariants. For example:

Example: There are $n$ lamps arranged (evenly spaced) in a circle. Initially, one of them is turned on, and the rest are off. It is permitted to choose any regular polygon whose vertices are lamps which are all in the same state (either all on or all off), and change all of their states simultaneously. For which positive integers $n$ is it possible to turn all the lamps off after a finite number of such operations?

Solution: Take a primitive $n$th root $\zeta$ of unity. Then, starting with the lamp which is on, assign the weights $1, \zeta, \zeta^2, \cdots, \zeta^{n-1}$ to the lamps around the circle. Then, consider the quantity equal to the sum of all the weights of every lamp which is on. The given operation does not change this quantity. Therefore, it will always be equal to $1$, and it is impossible to turn all the lamps off, as that would require it changing to $0$.

Here are some problems which can be solved using coloring or weighting:

1. Let $a, b, m, n$ be positive integers such that an $a \times b$ rectangle can be tiled by $n \times 1$ and $1 \times m$ rectangles (no rotations allowed). Prove that $n | a$ or $m | b$.

2. A rectangle is called extra tricky if one of its side lengths is an integer. Prove that if a rectangle can be partitioned into finitely many extra tricky rectangles, then it is itself extra tricky.

3. There are $n$ lamps arranged (evenly spaced) in a circle. Initially, one of them is turned on, and the rest are off. It is permitted to choose any regular polygon whose vertices are lamps (not necessarily all in the same state), and change all of their states simultaneously. For which positive integers $n$ is it possible to turn all the lamps off after a finite number of such operations?

4. (USAMO 2008) Let $ n$ be a positive integer. Denote by $ S_n$ the set of points $ (x, y)$ with integer coordinates such that
\[ \left|x\right| + \left|y + \frac {1}{2}\right| < n
\]
A path is a sequence of distinct points $ (x_1 , y_1 ), (x_2 , y_2 ), \ldots , (x_\ell, y_\ell)$ in $ S_n$ such that, for $ i = 2, \ldots , \ell$, the distance between $ (x_i , y_i )$ and $ (x_{i - 1} , y_{i - 1} )$ is $ 1$ (in other words, the points $ (x_i , y_i )$ and $ (x_{i - 1} , y_{i - 1} )$ are neighbors in the lattice of points with integer coordinates). Prove that the points in $ S_n$ cannot be partitioned into fewer than $ n$ paths (a partition of $ S_n$ into $ m$ paths is a set $ \mathcal{P}$ of $ m$ nonempty paths such that each point in $ S_n$ appears in exactly one of the $ m$ paths in $ \mathcal{P}$).

Elementary Properties of Cyclotomic Polyomials

by HroK, Aug 4, 2010, 10:42 PM

This PDF gives a fairly thorough introduction to elementary properties of cyclotomic polynomials, as well as examples of problems using them; it will be redundant to restate and reprove them in this blog post. However, one very useful property mentioned in the PDF that was not emphasized much shall be proven below:

Claim: Let $p$ be a prime, let $n = p^r k$ with $p \not | k$, and let $a$ be any positive integer. Then if $p | \Phi_n(a)$, the order of $a$ mod $p$ is equal to $k$.
Proof: We will first prove this in the case that $r = 0$. Let $e$ be the order of $a$ mod $p$. Since $p | a^k - 1$, $e | k$. Suppose for the sake of contradiction that $e < k$. Since $x^k - 1 = \prod_{d | n} \Phi_d(x)$ for all $x$, and $p | \Phi_e(a), \Phi_k(a)$, $(x-a)$ is a double root of $x^k - 1$ mod $p$, giving $p | k$. This is a contradiction, so $e = k$, as desired.

If $r > 0$, we have that $\Phi_n(a) = \frac{\Phi_k(a^{p^r})}{\Phi_k(a^{p^{r-1}})}$. If $p | \Phi_n(a)$, $p | \Phi_k(a^{p^r})$. $p \not | k$, so by the above, the order of $a^{p^r}$ mod $p$ is just $k$. But $a^{p^r} \equiv a \pmod{p}$, so our claim is proven.

Problems
  • Suppose $a$ and $b$ are positive integers distinct from 1, such that $a^n - 1$ and $b^n - 1$ have the same set of prime factors for all positive $n$. Show that the orders of $a$ and $b$ modulo $p$ are the same (or do not exist) for all primes $p$.
  • Let $x$, $m$, and $n$ be positive integers. Show that
    $ \frac{(x^{n+1}-1)(x^{n+2} - 1) \cdots (x^{n+m}-1)}{(x-1)(x^2-1) \cdots (x^m - 1)} $
    is always an integer.
This post has been edited 2 times. Last edited by HroK, Aug 5, 2010, 2:06 AM

Lifting the Exponent

by HroK, Aug 3, 2010, 9:36 PM

Hello. I am now going to discuss a theorem which is widely applicable to Olympiad multiplicative number theory problems.

Definition: For a prime $p$ and a nonzero rational number $n$, the $p$-adic valuation of $n$, denoted $v_p(n)$, is the exponent of $p$ in the prime factorization of $n$. For example, $v_2(96) = 5$ and $v_3\left(\frac{2}{9}\right) = -2$.

The $p$-adic valuation satisfies the important property that $v_p(mn) = v_p(m) + v_p(n)$. It also satisfies the relation $v_p(a+b) = \min\{v_p(a), v_p(b)\}$ for $v_p(a) \neq v_p(b)$.

Theorem (Lifting the Exponent Lemma, a.k.a. Mihai's Lemma): Let $p$ be an odd prime, and let $a$ be a rational number not equal to $1$ and such that $v_p(a - 1) > 0$. Then, for any positive integer $n$, \[v_p(a^n - 1) = v_p(a-1) + v_p(n).\]

(Equivalently, let $p$ be an odd prime and $a, b$ be two integers not divisible by $p$ such that $p | a - b$. Then, $v_p(a^n - b^n) = v_p(a - b) + v_p(n)$ for all positive integers $n$.)

Proof:

We proceed by induction on $v_p(n)$. We start with the base case $v_p(n) = 0$. Letting $v_p(a - 1) = r$, and $a = kp^r + 1$ for some rational number $k$ with $v_p(k) = 0$, we have
\[
\begin{align*}
a^n - 1 &= (kp^r + 1)^n - 1\\
&= \left(1 + nkp^r + \binom{n}{2} k^2 p^{2r} + \binom{n}{3} k^3 p^{3r} + \cdots\right) - 1 \\
&= p^r\left(nk+\binom{n}{2}k^2p^r + \binom{n}{3} k^3 p^{2r}+ \cdots\right).
\end{align*}\]
Since $v_p(n) = 0$ and $v_p(k) = 0$, $nk$ has a $p$-adic valuation of $0$. Additionally, $\binom{n}{2}k^2p^r + \binom{n}{3} k^3 p^{2r}+ \cdots$ has positive $p$-adic valuation. Therefore, by the properties of the $p$-adic valuation listed above, $nk+\binom{n}{2}k^2p^r + \binom{n}{3} k^3 p^{2r}+ \cdots$ has zero $p$-adic valuation. This means that the $p$-adic valuation of $a^n - 1$ is equal to the $p$-adic valuation of $p^r$, which is $r$, and the base case is complete.

If $v_p(n) > 0$ (the inductive step), then $p | n$. Furthermore, by the inductive hypothesis, $v_p(a^{n/p} - 1) = v_p(a - 1) + v_p(n) - 1$. Therefore, it is sufficient to prove that $v_p(a^n - 1) = v_p(a^{n/p} - 1) + 1$. Let $b = a^{n/p}$, and let $r = v_p(b - 1)$. Write $b = kp^r + 1$, where $v_p(k) = 0$. Then,
\[
\begin{align*}
a^n - 1 &= b^p - 1\\
&= (kp^r + 1)^p - 1 \\
&= \left(1 + pkp^r + \binom{p}{2}k^2p^{2r} + \binom{p}{3}k^3p^{3r} + \cdots\right) - 1 \\
&=  pkp^r + \binom{p}{2}k^2p^{2r} + \binom{p}{3}k^3p^{3r} + \cdots
\end{align*}\]
It is clear that the first term in this sum has a $p$-adic valuation of $r + 1$ and that the rest of the terms in this sum have $p$-adic valuation greater than $r + 1$. Therefore, the $p$-adic valuation of this sum is equal to $r + 1$. The induction is complete.

Now, let us demonstrate a use of this theorem.

Example. Prove that if $n$ is a positive integer, then $2$ is a primitive root mod $3^n$.
Solution. Clearly, $2 = \text{ord}_{3}(2) | \text{ord}_{3^n}(2)$. Therefore, $\text{ord}_{3^n}(2) = 2 \text{ord}_{3^n}(4)$. We have $3^n | 4^{\text{ord}_{3^n}(4)} - 1$. By the Lifting the Exponent Lemma, $v_3(\text{ord}_{3^n}(4)) + v_p(4 - 1)= v_3(4^{\text{ord}_{3^n}(4)} - 1)\geq n$, so $v_3(\text{ord}_{3^n}(4))  \geq n - 1$, so $3^{n - 1}|\text{ord}_{3^n}(4)$, so $2\cdot 3^{n - 1}|\text{ord}_{3^n}(2)$. But we also have $\text{ord}_{3^n}(2)|\varphi(3^n)=2 \cdot 3^{n-1}$. Therefore, $2\cdot 3^{n - 1}=\text{ord}_{3^n}(2)=\varphi(3^n)$ so we're done.

Problems!
  1. Prove the properties of the $p$-adic valuation listed above.
  2. Let $a$ be a rational number not equal to $1$ and such that $v_2(a - 1) \geq 2$. Then, prove that for any positive integer $n$, \[v_2(a^n - 1) = v_2(a-1) + v_2(n).\]
  3. Show that if $g$ is an integer that is a primitive root modulo $p^2$ for some prime $p$, then $g$ is a primitive root modulo $p^k$, for all positive integers $k$.
  4. (IMO 1990) Find all positive integers $n$ such that $n^2 | 2^n + 1$.
  5. (IMO 2000) Does there exist a positive integer $n$ with exactly 2000 prime divisors such that $n | 2^n + 1$?
  6. Prove that if $a, b$ are positive integers such that $a^n - b^n$ is a perfect power for all sufficiently large $n$, then $a = b$. (Amol Aggarwal)
  7. Find all solutions in positive integers $(x,y,m,n)$ to $x^n + y^n = (x+y)^m$.
  8. Prove that if $a$ is a positive integer greater than $1$, then $v_q(a^{q - 1} - 1)$ is odd for infinitely many primes $q$.
  9. (Open) Prove or disprove that if $a$ is a positive integer greater than $1$, then $v_q(a^{q - 1} - 1)=1$ for infinitely many primes $q$.

Usage note: While this lemma is well-known, it requires proof if cited on an Olympiad. Furthermore, this theorem is almost always called the "Lifting the Exponent Lemma"; it is almost never called "Mihai's lemma."

Click to reveal hidden text
This post has been edited 7 times. Last edited by HroK, Aug 4, 2010, 10:36 PM

Chromatic Number

by HroK, Jul 28, 2010, 9:50 PM

So, I was writing some stuff to give to some people I was teaching, and I decided it would be easier to upload it onto an AoPS blog.

Definition: the chromatic number of a simple graph is the smallest positive integer $k$ such that the vertices of the graph can be colored in $k$ colors such that no two vertices of the same color are adjacent.

For example, the chromatic number of the complete graph $K_n$ is $n$, because no two vertices can be colored in the same color, but it is valid to color them all with different colors.

Clearly, the chromatic number of a graph is greater than or equal to the chromatic number of any subgraph of the graph.

We start with a weak bound on the chromatic number of a graph:

Lemma: If a finite graph has maximum degree $d$, then the chromatic number of the graph is at most $d+1$.
Proof: It is only necessary to prove that each vertex can be colored with one of $d+1$ colors such that no two vertices of the same color are adjacent. To do this, we color each vertex one by one. When we color a vertex, we make sure that we don't color it in the same color as any of the vertices adjacent to it which we have already colored. (This is possible because there are at most $d$ of those vertices, so they have at most $d$ colors among them.)

Chromatic numbers can help solve many problems.

Example: 1.There are $n$ people in a meeting, and all of them know $k$ other people. If $m$ is a positive integer from 1 to $k$, prove that we can find a set of at least $
\frac{nm}{k+1}$ people such that there are not $m+1$ people in the group that all know each other.

Solution: By our lemma, we know we can color the graph of people (where two people are adjacent if they know each other) in $k+1$ colors. Then, choose the $m$ colors which color the greatest number of people, and consider the set of all people which are colored in one of these $m$ colors. If you take any $m+1$ people from this set, two of them will have the same color and not be adjacent. Also, note that we chose at least $\frac{mn}{k+1}$ of the whole set of people at the meeting, so we are done.

Whenever a problem is about people or roads or other things and the connections between them, graph theory should be tried. And when the problem asks to prove that there exists a group of vertices satisfying certain conditions, chromatic number approaches often work.

Problems: (arranged in approximate difficulty)
1. Prove that if a directed graph has maximum out-degree $d$, then its chromatic number is at most $2d+1$.

2. Prove the six-color theorem: every planar graph can be colored in six colors.

3. (Original) In the United States, everyone hates exactly two other people. (Hatred is not mutual.) A person will accept being near one of the people they hate, but he/she will refuse to live near both people they hate. Prove that it is possible to tell each person to go to one of 3 cities so that nobody refuses to live where they are assigned to live.

4. (All-Russian Olympiad) In Russia, everyone has between 50 and 100 (inclusive) friends. Variety is good, so the government decides to give everyone a t-shirt so that every person will have 20 friends wearing different t-shirts. Prove that this can be done if the government owns 1331 kinds of t-shirts, and the government owns infinity of each kind.

5. (All-Russian Olympiad) We have a directed graph where each vertex has outdegree 2. Prove that exists a finite number k so that, no matter what the graph is, we can split the vertices into k sets such that each there are no edges between vertices in the same set and there cannot be both an edge from A to B and an edge from B to A if A and B are chosen from the k sets.

6. Can you prove problem 3 is k is replaced with 1014?

7. (Open) Consider the graph where the vertices are the points in the plane, connected if the distance between them is equal to one. Find the chromatic number of this graph.

8. (Open) Without using a computer, prove that a planar graph can be colored in 4 colors.
This post has been edited 4 times. Last edited by HroK, Aug 3, 2010, 8:43 PM

The blog of an IMO participant. I'm no longer focusing on contest math, and my remaining preparation will consist largely of posts on my blog. I hope you find my blog useful for learning.

avatar

HroK
Shouts
Submit
  • lte explanation!!

    by pog, Dec 30, 2021, 3:13 AM

  • very pro

    by 554183, Jul 12, 2021, 6:33 AM

  • Thanks for the LTE explanation!

    by AOPSuser216, Sep 28, 2020, 11:37 PM

  • Your LTE explanation has been beyond helpful! Thanks!

    by lamphead, Jul 26, 2020, 6:46 PM

  • Yep , that's nice :D

    by Kamran011, Mar 30, 2020, 10:52 AM

  • thanks for the great problems!

    by Awesome_guy, Mar 21, 2020, 8:52 PM

  • heellooo
    niccee blogggg

    by AlastorMoody, Jan 10, 2020, 2:43 AM

  • thanks for the info about LTE.

    by Focus1111, Oct 22, 2019, 9:40 PM

  • hi im aops_turtle

    by aops_turtle, Jun 14, 2019, 2:56 AM

  • not very nice...

    by dummy07, Jan 5, 2019, 2:07 AM

  • you are a nerd kid

    by Quaratinium, Oct 29, 2016, 1:30 AM

  • These posts are very helpful.

    by ThinkFlow, Aug 13, 2011, 4:30 AM

12 shouts
Tags
About Owner
  • Posts: 11
  • Joined: Jul 26, 2010
Blog Stats
  • Blog created: Jul 28, 2010
  • Total entries: 7
  • Total visits: 16155
  • Total comments: 1
Search Blog
a