Chaitanya's Random Pages

June 30, 2011

Aussie participation in the Australian Open singles draw

Filed under: sport — ckrao @ 12:12 pm

The following graph shows the proportion of entrants in the main singles draw in the Australian tennis Open dating back to 1969, the start of the Open Era.

In the early years the Australian Open did not have the same prestige as a grand slam tournament (with lower prize money and ranking points relative to other majors) that it does today, so the top overseas players were less inclined to travel to Australia during Christmas time for the event. In 1970 for example only 4 of the female entrants were not Australian and in 1976 all 8 quarter finalists were Australian! During the late 1970s Argentine Guillermo Vilas was a prominent overseas participant and won the event twice while players like Connors and Borg skipped the event. It looks like 1980 was the time that there was a push to see more of the top players  playing down under. Players like Ivan Lendl and Martina Navratilova participated for the first time that year.

In the late 1970s only 32 were in the women’s draw. This was up to 128 by the time the event moved to its present home in Melbourne (then Flinders) Park in 1988. During most of the 1990s there were 14-18 Aussie men and 10-13 Aussie women in the singles draws. Since 2004 there have only been 6-9 Australians in both the men’s and women’s draw.

(Data from http://en.wikipedia.org/wiki/Category:Australian_Open_%28tennis%29_by_year and links therein.)

June 27, 2011

Interesting quadratic diophantine equations

Filed under: mathematics — ckrao @ 9:26 pm

Let a and b be positive integers. Then

  1. if \displaystyle \frac{a^2 +b^2}{ab+1} = k is an integer, k is a perfect square.
  2. if \displaystyle \frac{a^2 +b^2}{ab-1} = k is an integer, k = 5.

The first problem was question 6 in the 1988 International Mathematical Olympiad. In this post we show these results, find the solutions (a,b) and look at how similar equations can be solved. The idea used is known in some circles as “Vieta jumping” or “root flipping” which is a form of descent, forming smaller solutions from bigger ones.

Solution of 1. (found in [1]) Fix k and rewrite the equation as

\displaystyle a^2 - kab + b^2 - k = 0.

By symmetry we may assume a \geq b. For all such pairs (a,b) of positive integers satisfying the equation, there is one (a_0, b_0) such that a_0 is minimal. Let f(x) = x^2 - kb_0x + b_0^2 - k. We know that a_0 is one root of this quadratic, and the other is given by

\displaystyle a_1 = kb_0 - a_0 = \frac{b_0^2 - k}{a_0}.\quad(1)

From the first equation, a_1 is an integer.

a) If a_1 < 0,

\displaystyle 0 = a_1^2 + b_0^2 - k(a_1b_0 + 1) > a_1^2 + b_0^2 > 0,

a contradiction. Hence a_1 \geq 0.

b) Suppose a_1 > 0. Then (a_1, b_0) satisfies the given equation and

\displaystyle a_1 = \frac{b_0^2 - k}{a_0} \leq \frac{a_0^2 - k}{a_0} < a_0.

However this contradicts the minimality assumption on a_0, so we conclude that a_1 = 0, and

\displaystyle k = \frac{a_1^2 +b_0^2}{a_1b_0+1} = \frac{b_0^2}{1} = b_0^2,

a perfect square. This completes the proof of 1.

The general solution of problem 1 is found by using the fact that if (a,b) is a solution, so too is (b,kb-a). The above argument showed that kb-a \leq a, so a smaller solution is obtained. This recurrence can be continued until we reach the minimal solution(a_0, b_0). From the above argument, applying the recurrence one more time gives (b_0,0). Then from the equation kb_0 - a_0 = a_1 = 0 we obtain a_0 = b_0^3. Reversing this recurrence gives us the solution (ka-b,a) = (b_0^2a - b, a) from (a,b), leading to the general solution being adjacent terms (x_{i+1}, x_i) of the sequence

\displaystyle x_1, x_2, x_3, x_4, \ldots = b_0, b_0^3, b_0^5 - b_0, b_0^7 - 2b_0^3, \ldots

where x_{i+1} = b_0^2x_i - x_{i-1} = kx_i - x_{i-1}, b_0 \in \mathbb{N}.

It can also be shown [1] that for any solution (a,b) of the equation, k is the square of the greatest common divisor of a and b.

Solution of 2. (found in [2]) Firstly we note that a^2 + b^2 \geq 2ab > 2ab - 2, so

\displaystyle k = \frac{a^2 + b^2}{ab - 1} > 2.\quad...(2)

We proceed as in the first problem. Assume a solution a_0 > b_0 with a_0 minimal (the case a_0 = b_0 can easily be shown to be impossible), then form the quadratic f(x) = x^2 - kb_0x + b_0^2 + k and instead of (1), arrive at the second root

\displaystyle a_1 = kb_0 - a_0 = \frac{b_0^2 + k}{a_0}.\quad...(3)

By the minimality assumption a_1 \geq a_0 > b_0. Hence b_0 is less than the roots of a positive quadratic polynomial, so f(b_0) > 0. Hence

\displaystyle 0 < f(b_0) = b_0^2 - kb_0^2 + b_0^2 + k = (2-k)b_0^2 + k,

from which

\displaystyle b_0^2 < \frac{k}{k-2} < 4,

where the second inequality follows from (2). As b_0 \in \mathbb{N} and b_0^2 < 4, we must have b_0 = 1. Hence

\displaystyle k = \frac{a_0^2 + 1}{a_0 - 1} = a_0 + 1 + \frac{2}{a_0 - 1},

from which a_0 = 2 or a_0 = 3 and in either case k = 5, as required.

As in problem 1, all solutions are found by a second order recurrence relation from the minimal solutions (2,1) and (3,1). In this case, the recurrence is x_{i+1} = 5x_i - x_{i-1}, leading to adjacent terms of either of the following two sequences:

1,2,9,43,206,…

1,3,14,67,321,…

More generally, if we wish to solve the equation

\displaystyle a^2 - kab + b^2 = n,

in integers a and b (where n and k are integers with k > 2), there are either no solutions or infinitely many solutions. As above, we use the fact that if (a,b) is a solution, so is (b,kb-a). Then we need to determine whether such a transformation makes the solution smaller and when the process terminates. Also if (a,b) is a solution, so is (-b,-a).

One partial generalisation of problem 1 (found in [3]) is:

If  0 \leq n \leq k+1, then there are solutions to a^2 - kab + b^2 = n, in integers a and b if and only if n is a perfect square.

To show this, if a_0 > b_0 > 0 is the solution with a_0 minimal, form f(x) = x^2 - kb_0x + b_0^2 - n, which has roots a_0 and kb_0 - a_0 = (b_0^2 - n)/a_0. By minimality, kb_0 - a_0 \leq 0 < a_0. The quadratic f(x) is decreasing for x < kb_0/2, and so if kb_0 - a_0 < 0,

\displaystyle 0 = f(kb_0 - a_0) \geq f(-1) = 1 + kb_0 + b_0^2 - n > 1 + k - j \geq 0.

From this contradiction, we conclude that kb_0 - a_0 = 0, leading to b_0^2 - n =0, so n is a perfect square. Conversely, if n = c^2, then (a,b) = (c,0) is a solution. This completes the proof. As before, all solutions can be found via a recurrence.

If n is negative, we can upper bound the minimal solution as follows. As in the proof of problem 2 above, f(b_0) > 0, which leads to

\displaystyle (k-2)b_0^2 < -n.

This gives an upper bound on b_0 on which to try out solutions. If no such b_0 exists, there are no solutions to the equation. The case of k = -n = 5 in problem 2 for example led to the bound 3b_0^2 < 5, from which b_0 = 1 was the sole candidate to try.

References and further reading

[1] Mathematical Olympiads, The 1988 Australian Scene

[2] Vieta Jumping related .. • Art of Problem Solving

[3] http://www.math.niu.edu/~rusin/known-math/00_incoming/quad_eqn

[4] N = (x^2 + y^2)/(1+xy) is a Square – Mathpages.com

June 25, 2011

The Djokovic 43-match winning streak

Filed under: sport — ckrao @ 1:04 pm

I had been meaning to write something about what I believe is the most impressive winning streak in men’s tennis in my 20+ years of following the game. In almost 6 months between December 2010 and May 2011 Novak Djokovic won 7 tournaments (including the Australian Open) as well as the Davis Cup final. The quality of Djokovic’s run is remarkable for the quality of opposition he had to defeat. At the time of writing Rafael Nadal has won 4 of the past 5 grand slam titles and has reached the final of all ATP World Tour Masters 1000 tournaments this year, yet right now he leads the rankings by a tiny margin (12070 points to 12005). Djokovic was able to conquer Nadal in those four ATP World Tour Masters 1000 finals, two of which were straight sets victories on clay. He won 10 matches against players in the top 5 including 4 against Nadal, 3 against Roger Federer (including the Australian Open Semi-Final in straight sets) and 2 against Andy Murray.

Other points of note:

  • The winning streak is the third best by men in the Open era, behind Vilas with 46 and Lendl with 44 (the all-time record is 95 by Bill Tilden, way back in 1924-5).
  • 26 of his wins came on hard court while 17 were on clay.
  • Djokovic picked up 7470 points during his streak (a grand slam tournament is worth 2000). Even if he did not play again this year he would most likely remain in the world’s top 5 at the end of the year.
  • He defeated 32 different players, only 8 of whom were outside the top 50.
  • In the 26th and 38th matches of his streak (against Nadal and Murray respectively) he was 2 points away from losing the match in the third set.
  • He had a total of nine 6-0 sets and seven tie-breaker sets, winning five of them.
  • He won 97 sets and lost 10 during the streak.

Here is a list of his wins (from not including 3 Hopman Cup wins), with results found via the ATP World Tour website.

Tournament, date and points Match # Opponent Name Opponent Ranking Score
Davis Cup Final, Serbia, 3/12/10 1 Giles Simon 42 6-3, 6-1, 7-5
2 Gael Monfils 12 6-2, 6-2, 6-4
2011
Australian Open, 17/1/11 3 Marcel Granollers 42 6-1, 6-3, 6-1
4 Ivan Dodig 81 7-5, 6-7(8), 6-0, 6-2
5 Viktor Troicki 27 6-2 RET
6 Nicolas Almagro 14 6-3, 6-4, 6-0
7 Tomas Berdych 6 6-1, 7-6(5), 6-1
8 Roger Federer 2 7-6(3), 7-5, 6-4
2000 points 9 Andy Murray 5 6-4, 6-2, 6-3
Dubai, 21/2/11 10 Michael Llodra 27 6-3, 6-3
11 Feliciano Lopez 41 6-3, 2-6, 6-4
12 Florian Mayer 38 7-5, 6-1
13 Tomas Berdych 7 6-7(5), 6-2, 4-2 RET
500 points 14 Roger Federer 2 6-3, 6-3
ATP World Tour Masters 1000 Indian Wells, 10/3/11 15 Andrey Golubev 39 6-0, 6-4
16 Ernest Gulbis 34 6-0, 6-1
17 Viktor Troicki 18 6-0, 6-1
18 Richard Gasquet 21 6-2, 6-4
19 Roger Federer 2 6-3, 3-6, 6-2
1000 points 20 Rafael Nadal 1 4-6, 6-3, 6-2
ATP World Tour Masters 1000 Miami, 23/3/11 21 Denis Istomin 54 6-0, 6-1
22 James Blake 173 6-2, 6-0
23 Viktor Troicki 17 6-3, 6-2
24 Kevin Anderson 40 6-4, 6-2
25 Mardy Fish 15 6-3, 6-1
1000 points 26 Rafael Nadal 1 4-6, 6-3, 7-6(4)
Start of clay court season
Belgrade, 25/4/11 27 Adrian Ungur 175 6-2, 6-3
28 Blaz Kavcic 85 6-3, 6-2
250 points 29 Feliciano Lopez 37 7-6(4), 6-2 (Janko Tipsarevic withdrew from SF)
ATP World Tour Masters 1000 Madrid, 1/5/11 30 Kevin Anderson 35 6-3, 6-4
31 Guillermo Garcia-Lopez 29 6-1, 6-2
32 David Ferrer 6 6-4, 4-6, 6-3
33 Thomaz Bellucci 36 4-6, 6-4, 6-1
1000 points 34 Rafael Nadal 1 7-5, 6-4
ATP World Tour Masters 1000 Rome, 8/5/11 35 Lukasz Kubot 141 6-0, 6-3
36 Stanislas Wawrinka 14 6-4, 6-1
37 Robin Soderling 5 6-3, 6-0
38 Andy Murray 4 6-1, 3-6, 7-6(2)
1000 points 39 Rafael Nadal 1 6-4, 6-4
Roland Garros, 22/5/11 40 Thiemo de Bakker 71 6-2, 6-1, 6-3
41 Victor Hanescu 60 6-4, 6-1, 2-3 RET
42 Juan Martin Del Potro 26 6-3, 3-6, 6-3, 6-2
720 points 43 Richard Gasquet 16 6-4, 6-4, 6-2

(Fabio Fognini withdrew from the QF at Rolland Garros before Roger Federer ended the streak with a 6-7(5), 3-6, 6-3, 6-7(5) win)

Further reading:

Tennis – ATP World Tour – Novak Djokovic 39-Match Win Streak – By The Numbers

Djokovic’s Streak – By The Numbers | Tennis Panorama

The Dominant Djokovic Streak – WSJ Blogs

+ 40-match winning streak, which one the most impressive? – MensTennisForums.com

The end of Djokovic’s 43-match winning streak | Voo de Mar

NOVAK DJOKOVIC ALWAYS HAD THE TALENT AND DRIVE TO BECOME – 05.23.11 – SI Vault

Novak Djokovic’s 2011 among greatest tennis years ever – ESPN

Greatest Matches of Novak Djokovic’s 43 Match Winning Streak – Top Ten List


June 18, 2011

More on the sums of squares

Filed under: mathematics — ckrao @ 1:49 pm

In my previous mathematical post I took a look at the classical result that an odd prime can be written as the sum of two squares if and only if it is 1 modulo 4. One of the proofs used unique factorisation in the Gaussian integers, and this approach in fact shows that the prime’s representation as the sum of two squares is unique (up to sign and ordering). As an example, take p = 13. In the Gaussian integers its factors (3 + 2i) and (3 – 2i) are irreducible since their norm 13 is prime. To see this, if 3+2i = ab where a and b are Gaussian integers each with norm > 1, then taking norms of both sides leads to a contradiction that a prime number is the product of two integers greater than 1. Hence 3+2i (and similarly 3-2i) is irreducible. (By unique factorisation, the factors are also prime.) Hence 13 only factors as (3+2i)(3-2i) (up to multiplication by units) leading to the unique representation 13 = 3^2 + 2^2.

If we want to find representations of a number as the sum of two squares we can factorise it in the Gaussian integers, and then separate the factors into two piles so that a factor and its complex conjugate are not in the same pile. Then multiply out the factors in each pile. If there are many factors, then many ways of forming the piles may be possible. If however you see powers of 2, there is no need to permute its factors (1+i) and (1-i) as the difference between multiplication by (1+i) and by (1-i) is simply a 90 degree rotation in the complex plane.

To illustrate this, suppose we wish to write 130 as the sum of two squares in all possible ways.

Firstly we have

\begin{array} {lcl} 130 = 2.5.13 &=& (1+i)(1-i)(2 + i)(2-i)(3+2i)(3-2i)\\ &=& [(1+i)(2+i)(3+2i)][(1-i)(2-i)(3-2i)]\\ &=& (-3 + 11i)(-3-11i)\\ &=& 3^2 + 11^2.\end{array}

Then if we try

2.5.13 = [(1-i)(2+i)(3+2i)][(1+i)(2-i)(3-2i)] = (11 + 3i)(11-3i) = 11^2 + 3^2,

we arrive at the same solution as before.

Instead anchor the (1-i), (1+i) factors and permute the others. There is only one other possibility in this example:

2.5.13 = [(1+i)(2-i)(3+2i)][(1-i)(2+i)(3-2i)] = (7 + 9i)(7 - 9i) = 7^2 + 9^2

This helps explain the formula for the number of ways that n can be decomposed into the sum of two squares (given at the end of the previous related post) and why it did not depend on the power of 2 in its prime factorisation. It can be shown that the number of ways of writing n = a^2 + b^2 with a > 0, b \geq 0 is also given by the interesting formula

\displaystyle \sum_{\substack {d|n\\ d \equiv 1 \bmod 4}} 1 - \sum_{\substack {d|n\\ d \equiv 3 \bmod 4}} 1 .

That is, it is the number of divisors of n congruent to 1 modulo 4 minus those congruent to 3 modulo 4. See [1, p279] for a proof using Dirichlet multiplication, but try proving it yourself first if interested.

Going beyond a^2 + b^2

The above factorisation idea can be used when writing a positive integer n in the form a^2 + 2b^2 or a^2 + 3b^2. Instead of working in the Gaussian integers, we now factorise n in the rings \mathbb{Z}[\sqrt{-2}] or \mathbb{Z}[\omega = e^{2\pi i /3}] (the Eisenstein integers consisting numbers of the form a + b\omega) respectively. The identity (a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2 (multiplication in \mathbb{Z}[i]) generalises to

\displaystyle (a^2 + kb^2)(c^2 + kd^2) = (ac - kbd)^2 + k(ad + bc)^2    (multiplication in \mathbb{Z}[\sqrt{-k}]).

Hence it is enough to decompose n into a product of primes and then rearrange terms as before. For example 99 can be written in the form x^2 + 2y^2 in three ways (ignoring sign), since

\begin{array}{lcl}99 = 3^2.11 &=& (1 + \sqrt{-2})^2 (1 - \sqrt{-2})^2(3 + \sqrt{-2})(3 - \sqrt{-2})\\&=&[(1 + \sqrt{-2})^2(3 + \sqrt{-2})][(1 + \sqrt{-2})^2(3 + \sqrt{-2})] = (-7 + 5\sqrt{-2})(-7 - 5\sqrt{-2}) = 7^2 + 2.5^2\\&=&[3(3 + \sqrt{-2})][3(3 - \sqrt{-2})] = 9^2 + 2.3^2\\&=&[(1 + \sqrt{-2})^2(3 - \sqrt{-2})][(1 - \sqrt{-2})^2(3 + \sqrt{-2})] = (1+ 7 \sqrt{-2})(1-7\sqrt{-2}) = 1^2 + 2.7^2.\end{array}

It turns out that a prime p can be written in the form a^2 + 2b^2 if and only if p=2 or p is congruent to 1 or 3 modulo 8. Also a prime can be written in the form a^2 + 3b^2 if and only if p = 3 or p is congruent to 1 modulo 6. Factorisation in the Eisenstein integers can also be used to show that a prime can be written in the form a^2 + ab + b^2 if p is congruent to 1 modulo 3. The representation is not unique, since if (a,b) is a solution, so is (-a, a+b) or (a+b, -b) (and with their signs reversed). However, if these types of solutions are regarded as equivalent, then the solution is unique.

For similar results, see [2].

The factorisation method cannot be applied more generally to finding representations of the form a^2 + kb^2. We know that if a prime divides x^2 + y^2 or x^2 + 2y^2, then it necessarily has this form. However this is not true for x^2 + 5y^2 (e.g. 3 divides 21 = 1^2 + 5.2^2 but 3 is not of the form x^2 + 5y^2). The lack of unique factorisation in \mathbb{Z}[\sqrt{-5}] (for example 6 = 2.3 = (1 + \sqrt{-5})(1 + \sqrt{-5})) results in things breaking down.

In general, finding whether a prime can be written in the form p = a^2 + kb^2 (assuming p is odd and is not a factor of the discriminant of p) is equivalent to the following two conditions being satisfied:
(i) -k is a quadratic residue modulo p,
(ii) a polynomial congruence f(a) \equiv 0 \bmod p is satisfied modulo p. (It is also required that p is not a divisor of the discriminant of the polynomial f.)

To prove this for all k requires some high-powered maths (i.e. class field theory, then complex multiplication and modular functions to construct f). Condition (i) results from the fact that

a^2 + kb^2 \equiv 0 \bmod p  implies (a/b)^2 \equiv -k \bmod p.

In the above simpler cases, for k = 2 and 3 only condition (i) is needed (the modulo 8 and modulo 6 results follow from quadratic reciprocity), while for k=27 for example, it turns out that f(x) = x^3 - 2. See [3] for further details.

Further notes:

  • It is known that if c and d are given natural numbers, there is at most one representation of the prime p in the form cx^2 + dy^2 where x and y are natural numbers. A proof may be found in [4].
  • If n is large, there are non-brute-force computational algorithms for solving the Diophantine equation cx^2 + dy^2 = n, for example Cornacchia’s algorithm and the Hardy-Muscat-Williams algorithm [5].

The sum of squares is a special case of a binary quadratic form, about which there is a wealth of theory which I hope to learn to some extent in the coming months.

References and further reading

[1] K. Ireland, M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, 1990.

[2] Weisstein, Eric W. “Diophantine Equation–2nd Powers.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/DiophantineEquation2ndPowers.html

[3] D. A. Cox, Primes of the form x² + ny², John Wiley & Sons, 1989.

[4] http://math.stackexchange.com/questions/33125/factoring-numbers-of-the-binary-quadratic-form-in-two-different-ways

[5] K. Hardy, J. B. Muskat, K. Williams, A deterministic algorithm for solving n = ƒu² + gv² in coprime integers u and v, Math. Comp. 55 (1990), 327-343. Available here in pdf form.

[6] Q. Yuan, Annoying Precision blog entries: (1) From Gauss to Eisenstein,  (2) Three approaches to sums of squares

Blog at WordPress.com.

%d bloggers like this: