The steady state of mathematical research is to be completely stuck. It is a process that Charles Fefferman of Princeton, himself a onetime math prodigy turned Fields medalist, likens to "playing chess with the devil." The rules of the devil’s game are special, though: The devil is vastly superior at chess, but, Fefferman explained, you may take back as many moves as you like, and the devil may not. You play a first game, and, of course, "he crushes you." So you take back moves and try something different, and he crushes you again, "in much the same way." If you are sufficiently wily, you will eventually discover a move that forces the devil to shift strategy; you still lose, but — aha! — you have your first clue.Source: http://www.nytimes.com/2015/07/26/magazine/the-singular-mind-of-terry-tao.html
Tuesday, July 28, 2015
"The steady state of mathematical research is to be completely stuck."
Wednesday, July 8, 2015
Completions of Fields
We proved earlier that every valuation $\abs{\cdot}$ is equivalent to one that satisfies the triangle inequality. Thus $\abs{\cdot}$ gives $K$ the structure of a metric space by letting $\rho(x, y) = \abs{x - y}^r$.
Theorem Two valuations $\abs{\cdot}_1$ and $\abs{\cdot}_2$ induce the same topology on $K$ iff they are equivalent.
Proof From the definition of the topology, it is clear that if $\abs{x}_1^r = \abs{x}_2$, then $\abs{\cdot}_1$ and $\abs{\cdot}_2$ induce the same topology on $K$.
Now suppose $\abs{\cdot}_1$ and $\abs{\cdot}_2$ are nontrivial and induce the same topology on $K$ There exists an $x_0$ such that $\abs{x_0}_1 > 1$, and let $r = \frac{\log\abs{x_0}_2}{\log\abs{x_0}_1}$. I claim that this is the desired $r$. Since $\abs{x_0^{-n}}_1\to 0$, $x_0^{-n}\to 0$, so $\abs{x_0^{-n}}_2 \to 0$, which means that $\abs{x_0}_2 > 1$ as well. Thus $r > 0$.
Fix another $x\in K^\times$, and let $\epsilon = \log\abs{x}_2 - r\log\abs{x}_1$. Suppose for the sake of contradiction that $\epsilon \neq 0$. Since $\abs{\cdot}_1$ and $\abs{\cdot}_2$ are equivalent,
Fix another $x\in K^\times$, and let $\epsilon = \log\abs{x}_2 - r\log\abs{x}_1$. Suppose for the sake of contradiction that $\epsilon \neq 0$. Since $\abs{\cdot}_1$ and $\abs{\cdot}_2$ are equivalent,
\[ \abs{x_0^{e_i} x^{f_i}}_1\to 0 \iff \abs{x_0^{e_i} x^{f_i}}_2\to 0, \] or equivalently, \[ e_i\log\abs{x_0}_1 + f_i\log \abs{x}_1\to -\infty \iff r(e_i\log\abs{x_0}_1 + f_i \log\abs{x}_1) + \epsilon f_i\to -\infty.\] Let $f_n = -n\cdot \operatorname{sgn}(\epsilon)$, $e_n = \left\lceil \frac{-f_n\log\abs{x}_1}{\log \abs{x_0}_1} \right\rceil$. Then
\[ 0 \le e_i\log\abs{x_0}_1 + f_i\log \abs{x}_1 \le \abs{x_0}_1. \] However, \[ \epsilon f_i \le r(e_i\log\abs{x_0}_1 + f_i \log\abs{x}_1) + \epsilon f_i \le \epsilon f_i + r\abs{x_0}_1, \] so the first series does not converge to $-\infty$ while the second does, contradiction. Thus for all $x\in K^\times$, $\log\abs{x}_2 - r\log\abs{x}_1 = 0$. $\boxed{}$
Given a valuation $v$ on $K$, we can complete $K$ with respect to the topology induced by $v$ to get a new metric space $K_v$.
Proposition There is a unique way to give $K_v$ the structure of a field such that addition and multiplication are continuous with respect to the valuation $v$.
Proof Note that multiplication and addition are clearly continuous on $K$, so they extend uniquely to multiplication and addition on $K$. Thus $K_v$ already has a ring structure. It suffices to show that $K_v$ has inverses. This is also not hard to show and is left as an exercise to the reader.$\boxed{}$
Proposition Suppose $v$ is a ((non-)Archimedian) valuation on $K$. Then $v$ extends uniquely to a ((non-)Archimedian) valuation on $K_v$.
Proof Obvious by the continuity of $v$. The details are left as an exercise to the reader. $\boxed{}$.
Theorem (Big Ostrowski, Part II) Suppose $v$ is an Archimedian valuation on the number field $K$. Then there exist an embedding $\sigma: K\to \BC$ and a real number $r > 0$ such that $\abs{x}_v = \abs{\sigma(x)}_{\BC}^r$.
Proof Let $K_v$ be the completion of $K$ with respect to $K$. It suffices to show that there exists a valuation-preserving isomorphism from either $K_v\to \BR$ or $K_v\to \BC$.
Note that since we have an embedding $\BQ\to K$ and the restriction of $v$ onto $\BQ$ must be the absolute value norm on $\BQ$, there exists an embedding $\BQ\to K_v$ that extends uniquely to an embedding $\BR\simeq \BQ_v \to K_v$. Thus it suffices to show that every element of $K_v$ has degree at most 2 over $\BR$.
Let $x\in K_v$, and define the function $f_x: \BC\to \BR$ as $z\mapsto \abs{x^2 - (z + \bar{z})x + z\cdot \bar{z}}_{\BC}$. Note that $x$ having degree at most 2 over $\BR$ is equivalent to $f_x(z) = 0$ for some $z\in \BC$, so suppose for the sake of contradiction that $f_x$ never hits 0. Note that the region $\{z: \abs{f_x(z)}_{\BC} < R\}$ is bounded for any $R$. Thus $f_x$ attains a minimum $r>0$ at $z_0$. Since $f_x^{-1}(r)$ is closed and bounded, it is compact. Thus we can pick $z_0$ such that $\abs{z_0}_{\BC}$ is maximal.
Let $0 < \epsilon < r$ be a real number, and let $z_1$ be a root of $z^2 - (z_0 + \bar{z}_0)z+ z_0\cdot \bar{z}_0 + \epsilon = 0$. Since this is also a real quadratic, we have $\abs{z_1}_{\BC}^2 = z_1\cdot \bar{z_1} = z_0\cdot \bar{z}_0 + \epsilon > \abs{z_0}_{\BC}^2$, so $f_x(z_1) > r$.
Now consider $g_n(t) = (t^2 - (z_0 + \bar{z}_0) t+ z_0\cdot \bar{z}_0)^n - (-\epsilon)^n\in \BR[t]$. Note that $g_n(t)$ can be factored uniquely into (real) linear terms and irreducible quadratic terms, so if $t_1, \ldots, t_{2n}\in \BC$ are the roots of $g_n$, then \[ g_n(x)^2 = g_n(t)\cdot \overline{g_n(t)} = \prod_{i = 1}^{2n} (t^2 - (t_i + \bar{t_i})t + t_i\cdot \bar{t_i}) \] Furthermore, $z_1$ is always a root of $g_n(t)$, so without loss of generality $z_1 = t_1$. Thus \[ \abs{g_n(x)}^2_v = \prod_{i = 1}^{2n} \abs{x^2 - (t_i + \bar{t_i})x + t_i\cdot \bar{t_i}}_v\ge f_x(z_1)\cdot r^{2n - 1} \] However, $g_n(x) = r^n - (-\epsilon)^n$. Thus $f_x(z_1)\le \frac{(r^n + (-\epsilon)^n)^2}{r^{2n - 1}}$, so taking $n\to\infty$ gives $f_x(z_1) \le r$, contradiction.$\boxed{}$
Given a valuation $v$ on $K$, we can complete $K$ with respect to the topology induced by $v$ to get a new metric space $K_v$.
Proposition There is a unique way to give $K_v$ the structure of a field such that addition and multiplication are continuous with respect to the valuation $v$.
Proof Note that multiplication and addition are clearly continuous on $K$, so they extend uniquely to multiplication and addition on $K$. Thus $K_v$ already has a ring structure. It suffices to show that $K_v$ has inverses. This is also not hard to show and is left as an exercise to the reader.$\boxed{}$
Proposition Suppose $v$ is a ((non-)Archimedian) valuation on $K$. Then $v$ extends uniquely to a ((non-)Archimedian) valuation on $K_v$.
Proof Obvious by the continuity of $v$. The details are left as an exercise to the reader. $\boxed{}$.
Theorem (Big Ostrowski, Part II) Suppose $v$ is an Archimedian valuation on the number field $K$. Then there exist an embedding $\sigma: K\to \BC$ and a real number $r > 0$ such that $\abs{x}_v = \abs{\sigma(x)}_{\BC}^r$.
Proof Let $K_v$ be the completion of $K$ with respect to $K$. It suffices to show that there exists a valuation-preserving isomorphism from either $K_v\to \BR$ or $K_v\to \BC$.
Note that since we have an embedding $\BQ\to K$ and the restriction of $v$ onto $\BQ$ must be the absolute value norm on $\BQ$, there exists an embedding $\BQ\to K_v$ that extends uniquely to an embedding $\BR\simeq \BQ_v \to K_v$. Thus it suffices to show that every element of $K_v$ has degree at most 2 over $\BR$.
Let $x\in K_v$, and define the function $f_x: \BC\to \BR$ as $z\mapsto \abs{x^2 - (z + \bar{z})x + z\cdot \bar{z}}_{\BC}$. Note that $x$ having degree at most 2 over $\BR$ is equivalent to $f_x(z) = 0$ for some $z\in \BC$, so suppose for the sake of contradiction that $f_x$ never hits 0. Note that the region $\{z: \abs{f_x(z)}_{\BC} < R\}$ is bounded for any $R$. Thus $f_x$ attains a minimum $r>0$ at $z_0$. Since $f_x^{-1}(r)$ is closed and bounded, it is compact. Thus we can pick $z_0$ such that $\abs{z_0}_{\BC}$ is maximal.
Let $0 < \epsilon < r$ be a real number, and let $z_1$ be a root of $z^2 - (z_0 + \bar{z}_0)z+ z_0\cdot \bar{z}_0 + \epsilon = 0$. Since this is also a real quadratic, we have $\abs{z_1}_{\BC}^2 = z_1\cdot \bar{z_1} = z_0\cdot \bar{z}_0 + \epsilon > \abs{z_0}_{\BC}^2$, so $f_x(z_1) > r$.
Now consider $g_n(t) = (t^2 - (z_0 + \bar{z}_0) t+ z_0\cdot \bar{z}_0)^n - (-\epsilon)^n\in \BR[t]$. Note that $g_n(t)$ can be factored uniquely into (real) linear terms and irreducible quadratic terms, so if $t_1, \ldots, t_{2n}\in \BC$ are the roots of $g_n$, then \[ g_n(x)^2 = g_n(t)\cdot \overline{g_n(t)} = \prod_{i = 1}^{2n} (t^2 - (t_i + \bar{t_i})t + t_i\cdot \bar{t_i}) \] Furthermore, $z_1$ is always a root of $g_n(t)$, so without loss of generality $z_1 = t_1$. Thus \[ \abs{g_n(x)}^2_v = \prod_{i = 1}^{2n} \abs{x^2 - (t_i + \bar{t_i})x + t_i\cdot \bar{t_i}}_v\ge f_x(z_1)\cdot r^{2n - 1} \] However, $g_n(x) = r^n - (-\epsilon)^n$. Thus $f_x(z_1)\le \frac{(r^n + (-\epsilon)^n)^2}{r^{2n - 1}}$, so taking $n\to\infty$ gives $f_x(z_1) \le r$, contradiction.$\boxed{}$
Saturday, July 4, 2015
Archimedian Valuations on Number Fields
Definition A valuation $\abs{\cdot}$ is non-Archimedian if $\abs{x + y} \le \max(\abs{x}, \abs{y})$. Otherwise, we say that the valuation is Archimedian.
Remark It's not hard to see that if $\abs{\cdot}$ is Archimedian, then so is $\abs{\cdot}^r$ for any real number $r$.
Example(s) If $K = \BQ$, for any prime $p$, $\abs{\cdot}_p$ is non-Archimedian, while $\abs{\cdot}_\infty$ is Archimedian.
Example Let $K$ be a number field, and suppose $\mf{p}$ is a prime ideal of $K$. For each $x$, let $v_{\mf{p}}(x)$ be the greatest integer $n$ such that $x\in \mf{p}^n$. Then the function given by $\abs{x} = \mc{N}(\mf{p})^{-v_{\mf{p}}(x)}$ is a non-Archimedian norm. (This is called the $\mf{p}$-adic valuation on $K$ and is denoted $\abs{\cdot}_{\mf{p}}$.)
Remark It's not hard to see that if $\abs{\cdot}$ is Archimedian, then so is $\abs{\cdot}^r$ for any real number $r$.
Example(s) If $K = \BQ$, for any prime $p$, $\abs{\cdot}_p$ is non-Archimedian, while $\abs{\cdot}_\infty$ is Archimedian.
Example Let $K$ be a number field, and suppose $\mf{p}$ is a prime ideal of $K$. For each $x$, let $v_{\mf{p}}(x)$ be the greatest integer $n$ such that $x\in \mf{p}^n$. Then the function given by $\abs{x} = \mc{N}(\mf{p})^{-v_{\mf{p}}(x)}$ is a non-Archimedian norm. (This is called the $\mf{p}$-adic valuation on $K$ and is denoted $\abs{\cdot}_{\mf{p}}$.)
Proposition A valuation $\abs{\cdot}$ is non-Archimedian if and only if there exists a real number $M$ such that $\abs{m} < M$ for all $m\in \BZ$. (i.e. bounded on the rational integers)
Proof Note that the proposition is unchanged by replacing $\abs{\cdot}$ with $\abs{\cdot}^r$ for any real number $r > 0$, so we may assume that $\abs{\cdot}$ satisfies the triangle inequality.
For one direction, if $\abs{\cdot}$ is non-Archimedian, then $\abs{m}\le \abs{1}$, so the boundedness condition clearly holds.
Now we prove the other direction. Suppose $\abs{m} < M$ for all $m\in \BZ$. Then
\[ \begin{align*} \abs{x + y}^n &= \abs{(x + y)^n} \\ &= \abs{\sum_{i = 0}^n \binom{n}{i} x^k y^{n-i}} \\ &\le \sum_{i = 0}^n \abs{\binom{n}{i}}\cdot \abs{x^k y^{n-i}}\\ &\le M(n + 1)\max(\abs{x}^n, \abs{y}^n) \end{align*} \] Thus $\abs{x + y}\le (M(n + 1))^{1 / n}\max(\abs{x}, \abs{y})$ for all positive integers $n$, so taking $n\to\infty$ gives $\abs{x + y}\le \max(\abs{x}, \abs{y})$. $\boxed{}$.
For the remainder of this post, suppose $K$ is a number field (i.e. a finite extension of $\BQ$). Let $\mathcal{O}_K$ denote the ring of integers in $K$.
Lemma Suppose $\abs{\cdot}$ is a non-Archimedian valuation on $K$. Then for all $x\in \mc{O}_K$, $\abs{x} \le 1$.
Proof Let the minimal polynomial of $x$ be $x^n + a_{n-1}x^{n-1} + \ldots + a_0$, where $a_0, \ldots, a_{n-1}\in \BZ$. Then $\abs{a_i}\le i$ for all $i$, so \[ \begin{align*} \abs{x}^n = \abs{x^n} &= \abs{\sum_{i = 0}^{n - 1}a_i x^i}\\ &\le \max_{0\le i\le n - 1} \abs{a_i x^i}\\ &\le \max_{0\le i\le n - 1} \abs{x}^i\\ &= \max(1, \abs{x}^{n-1}) \end{align*} \] This is only possible if $\abs{x} \le 1$. $\boxed{}$.
Theorem (Big Ostrowski, Part I) Suppose $\abs{\cdot}$ is a (nontrivial) non-Archimedian norm on $K$. Then $\abs{\cdot}$ is equivalent to $\abs{\cdot}_{\mf{p}}$ for some prime ideal $\mf{p}\subseteq \mc{O}_K$.
Proof The proof of this theorem very closely resembles the proof of the non-Archimedian case of Little Ostrowski's Theorem. However, instead of rational primes, we have prime ideals, and we have to make a little tweak with the class group. In any case....
Let $\abs{\cdot}$ be a non-Archimedian norm on $K$, let $I = \{x\in \mc{O}_K : \abs{x} < 1\}$. By the previous lemma, $I$ has to be a proper ideal of $\mc{O}_K$. Since $\abs{\cdot}$ is nontrivial, $I$ is also nonzero. Finally, if $xy\in I$, then either $x\in I$ or $y\in I$, so $I = \mf{p}$ for some prime ideal $\mf{p}$. It remains to show that $\abs{x} = c^{v_\mf{p}(x)}$ for some real number $0 < c < 1$.
Let $n = \abs{\mc{Cl}_K}$ be the size of the class group of $K$. Then for each prime ideal $\mf{q}$, there exists an $x_{\mf{q}}\in \mc{O}_K$ such that $\mf{q}^n = (x_{\mf{q}})$. In addition, we have \[\abs{x_{\mf{q}}} < 1\iff x_{\mf{q}}\in \mf{p} \iff \mf{q} = \mf{p}.\]Given an $x\in K$, we have that $(x) = \prod_{\mf{q}} \mf{q}^{v_{\mf{q}}(x)}$ is the unique factorization of the fractional ideal $K$ into prime ideals. Then \[(x^n) = \prod_{\mf{q}} \mf{q}^{nv_{\mf{q}}(x)} = \prod_{\mf{q}} (x_{\mf{q}})^{v_{\mf{q}}(x)}\implies x^n = \prod_{\mf{q}} x_{\mf{q}}^{v_{\mf{q}}(x)}.\] Thus \[\abs{x} = \abs{x^n}^{1/n} = \prod_{\mf{q}} \abs{x_{\mf{q}}}^{v_{\mf{q}}(x)} = \abs{x_{\mf{p}}}^{v_{\mf{q}}(x)/n},\] as desired. $\boxed{}$
Friday, July 3, 2015
Introduction to Valuations
Here we will introduce the notion of a valuation on a field
Definition Let $K$ be a field. A valuation $\abs{\cdot}$ is a map $K\to \BR^{\ge 0}$ such that the following constraints hold.
Theorem ([Little] Ostrowski's Theorem) When $K = \BQ$, all nontrivial valuations on $K$ are equivalent to either $\abs{\cdot}_\infty$ or $\abs{\cdot}_p$ for some prime $p$.
Proof First suppose $\abs{n}\le 1$ for all positive integers $n$. Set $I = \{n\in \BZ: \abs{n} < 1\}$; note that $I$ is a proper ideal of $\BZ$. Since $\abs{\cdot}$ is nontrivial, $I$ is nonempty, so $I = (n)$ for some positive integer $n > 1$. However, if $\abs{n} < 1$, then $\abs{p} < 1$ for some prime $p$ dividing $n$, which means that $p\in (n)$. The only way this is possible is if $n = p$, or $I = (p)$. Thus $\abs{q} = 1$ for all primes $q\neq p$, which means that $\abs{n} = \abs{p}^{v_p(n)}$ for all $n\in \BQ^\times$. As $\abs{p} < 1$, this is equivalent to the $p$-adic valuation.
Now suppose there exists an integer $m$ such that $\abs{m} > 1$. For every positive integer $n > 1$, we have that $m^k < n^{1 + \fl{\frac{k\log m}{\log n}}}$. Thus if we write out $m^k$ in base $n$ and use the triangle inequality we have \[ \abs{m}^k = \abs{m^k}\le (n-1)\left(1 + \fl{\frac{k\log m}{\log n}}\right)\max(1, \abs{n}^{ \fl{\frac{k\log m}{\log n}}}) \] As $k\to \infty$, $\abs{m}^k$ grows larger than $1 + \fl{\frac{k\log m}{\log n}}$, so we must have $\abs{n} > 1$ for all positive integers $n > 1$. In addition, taking $k\to \infty$ shows that for any pair of positive integers $m, n > 1$, \[ \abs{m}\le \abs{n}^{\displaystyle\frac{\log m}{\log n}}\implies \frac{\log\abs{m}}{\log m} = \frac{\log\abs{n}}{\log n} \] Thus there is a real number $r$ such that $\abs{n} = n^r$ for all positive integers $n$. Thus for all $x\in \BQ, \abs{x} = \abs{x}_\infty^r$. Furthermore, $\abs{n} > 1$ for all positive integers $n$, so $r > 1$. Thus $\abs{\cdot}$ is equivalent to $\abs{\cdot}_\infty$. $\boxed{}$
- $\abs{x} = 0$ if and only if $x = 0$.
- $\abs{xy} = \abs{x}\cdot \abs{y}$.
- There exists a real number $c$ such that for all $x,y\in K$, $\abs{x + y}\le c\max(\abs{x}, \abs{y})$.
Example Let $K = \BQ$. The function $\abs{\cdot}$ given by embedding $\BQ$ into $\BR$ and then taking absolute value is a valuation (henceforth we will denote this $\abs{\cdot}_\infty$. This notation is a little funky, but should make a more sense after seeing Ostrowski's theorem below).
Example / Exercise Let $K = \BQ$ and let $p$ be a rational prime. Let $v_p(x)$ be the exponent of the power of $p$ dividing $x$. Then the function given by $\abs{x} = p^{-v_p(x)}$ is a valuation on $\BQ$. (This is the standard $p$-adic valuation on $\BQ$, and is denoted $\abs{\cdot}_p$.)
Definition / Example The trivial valuation $\abs{\cdot}_0$ is the one that takes on the value of 1 on all of $K^\times$.
Proposition Suppose $\abs{\cdot}$ is a valuation on $K$, and let $r$ positive real number. Then $\abs{\cdot}^r$ is also a valuation on $K$.
Proof Obvious. $\boxed{}$
Definition Two nontrivial valuations $\abs{\cdot}_1$ and $\abs{\cdot}_2$ are equivalent if there exists a real number $r > 0$ such that $\abs{x}_1^r = \abs{x}_2$ for all $x\in K$.
Proposition Let $\abs{\cdot}$ be a valuation on $K$ such that property (3) holds with $c = 2$. Then $\abs{\cdot}$ satisfies the triangle inequality; i.e. $\abs{x + y} \le \abs{x} + \abs{y}$ for all $x, y\in K$.
Proof We are given that $\abs{x + y}\le 2\max(\abs{x}, \abs{y})$ for all $x, y\in K$. By induction we see that \[\abs{\sum_{i = 1}^{2^s} x_i}\le 2^s \max_{1\le i\le 2^s}\abs{x_i}\] for all positive integers $s$. In particular, if $2^{s - 1}\le n< 2^s$, \[ \abs{\sum_{i = 1}^{n} x_i}\le 2^s \max_{1\le i \le n}\abs{x_i} < 2n \max_{1\le i \le n}\abs{x_i} \] One immediate consequence is that $\abs{n} < 2n$ for all positive integers $n$. Now for all $x, y\in K$ and for all positive integers $n$, we have \[ \begin{align*} \abs{x + y}^n = \abs{(x + y)^n} &= \abs{\sum_{i = 0}^n \binom{n}{i} x_i y^{n - i}} \\ &\le 2(n + 1)\max_{0\le i\le n} \abs{\binom{n}{i} x^i y^{n - i}} \\ &\le 2(n + 1)\sum_{i = 0}^n \abs{\binom{n}{i} x^i y^{n - i}} \\ &\le 4(n + 1)\sum_{i = 0}^n \binom{n}{i} \abs{x^i y^{n - i}} \\ &= 4(n + 1)(\abs{x} + \abs{y})^n. \end{align*} \] Taking $n\to \infty$ gives $\abs{x + y}\le \abs{x} + \abs{y}$, as desired. $\boxed{}$
Corollary Let $\abs{\cdot}$ be a valuation on $K$. Then $\abs{\cdot}$ is equivalent to a valuation that satisfies the triangle inequality.
Proof Pick $c$ such that property (3) holds, and pick $r > 0$ such $c^r \le 2$. Then $\abs{\cdot}^r$ satisfies the triangle inequality. $\boxed{}$
Example / Exercise Let $K = \BQ$ and let $p$ be a rational prime. Let $v_p(x)$ be the exponent of the power of $p$ dividing $x$. Then the function given by $\abs{x} = p^{-v_p(x)}$ is a valuation on $\BQ$. (This is the standard $p$-adic valuation on $\BQ$, and is denoted $\abs{\cdot}_p$.)
Definition / Example The trivial valuation $\abs{\cdot}_0$ is the one that takes on the value of 1 on all of $K^\times$.
Proposition Suppose $\abs{\cdot}$ is a valuation on $K$, and let $r$ positive real number. Then $\abs{\cdot}^r$ is also a valuation on $K$.
Proof Obvious. $\boxed{}$
Definition Two nontrivial valuations $\abs{\cdot}_1$ and $\abs{\cdot}_2$ are equivalent if there exists a real number $r > 0$ such that $\abs{x}_1^r = \abs{x}_2$ for all $x\in K$.
Proposition Let $\abs{\cdot}$ be a valuation on $K$ such that property (3) holds with $c = 2$. Then $\abs{\cdot}$ satisfies the triangle inequality; i.e. $\abs{x + y} \le \abs{x} + \abs{y}$ for all $x, y\in K$.
Proof We are given that $\abs{x + y}\le 2\max(\abs{x}, \abs{y})$ for all $x, y\in K$. By induction we see that \[\abs{\sum_{i = 1}^{2^s} x_i}\le 2^s \max_{1\le i\le 2^s}\abs{x_i}\] for all positive integers $s$. In particular, if $2^{s - 1}\le n< 2^s$, \[ \abs{\sum_{i = 1}^{n} x_i}\le 2^s \max_{1\le i \le n}\abs{x_i} < 2n \max_{1\le i \le n}\abs{x_i} \] One immediate consequence is that $\abs{n} < 2n$ for all positive integers $n$. Now for all $x, y\in K$ and for all positive integers $n$, we have \[ \begin{align*} \abs{x + y}^n = \abs{(x + y)^n} &= \abs{\sum_{i = 0}^n \binom{n}{i} x_i y^{n - i}} \\ &\le 2(n + 1)\max_{0\le i\le n} \abs{\binom{n}{i} x^i y^{n - i}} \\ &\le 2(n + 1)\sum_{i = 0}^n \abs{\binom{n}{i} x^i y^{n - i}} \\ &\le 4(n + 1)\sum_{i = 0}^n \binom{n}{i} \abs{x^i y^{n - i}} \\ &= 4(n + 1)(\abs{x} + \abs{y})^n. \end{align*} \] Taking $n\to \infty$ gives $\abs{x + y}\le \abs{x} + \abs{y}$, as desired. $\boxed{}$
Corollary Let $\abs{\cdot}$ be a valuation on $K$. Then $\abs{\cdot}$ is equivalent to a valuation that satisfies the triangle inequality.
Proof Pick $c$ such that property (3) holds, and pick $r > 0$ such $c^r \le 2$. Then $\abs{\cdot}^r$ satisfies the triangle inequality. $\boxed{}$
Theorem ([Little] Ostrowski's Theorem) When $K = \BQ$, all nontrivial valuations on $K$ are equivalent to either $\abs{\cdot}_\infty$ or $\abs{\cdot}_p$ for some prime $p$.
Proof First suppose $\abs{n}\le 1$ for all positive integers $n$. Set $I = \{n\in \BZ: \abs{n} < 1\}$; note that $I$ is a proper ideal of $\BZ$. Since $\abs{\cdot}$ is nontrivial, $I$ is nonempty, so $I = (n)$ for some positive integer $n > 1$. However, if $\abs{n} < 1$, then $\abs{p} < 1$ for some prime $p$ dividing $n$, which means that $p\in (n)$. The only way this is possible is if $n = p$, or $I = (p)$. Thus $\abs{q} = 1$ for all primes $q\neq p$, which means that $\abs{n} = \abs{p}^{v_p(n)}$ for all $n\in \BQ^\times$. As $\abs{p} < 1$, this is equivalent to the $p$-adic valuation.
Now suppose there exists an integer $m$ such that $\abs{m} > 1$. For every positive integer $n > 1$, we have that $m^k < n^{1 + \fl{\frac{k\log m}{\log n}}}$. Thus if we write out $m^k$ in base $n$ and use the triangle inequality we have \[ \abs{m}^k = \abs{m^k}\le (n-1)\left(1 + \fl{\frac{k\log m}{\log n}}\right)\max(1, \abs{n}^{ \fl{\frac{k\log m}{\log n}}}) \] As $k\to \infty$, $\abs{m}^k$ grows larger than $1 + \fl{\frac{k\log m}{\log n}}$, so we must have $\abs{n} > 1$ for all positive integers $n > 1$. In addition, taking $k\to \infty$ shows that for any pair of positive integers $m, n > 1$, \[ \abs{m}\le \abs{n}^{\displaystyle\frac{\log m}{\log n}}\implies \frac{\log\abs{m}}{\log m} = \frac{\log\abs{n}}{\log n} \] Thus there is a real number $r$ such that $\abs{n} = n^r$ for all positive integers $n$. Thus for all $x\in \BQ, \abs{x} = \abs{x}_\infty^r$. Furthermore, $\abs{n} > 1$ for all positive integers $n$, so $r > 1$. Thus $\abs{\cdot}$ is equivalent to $\abs{\cdot}_\infty$. $\boxed{}$
Sunday, June 28, 2015
Wednesday, June 24, 2015
Problems to Give to Your Enemies
- There are 9 cards numbered 1 to 9. Ada and Bob play a game where they alternate selecting cards (without replacement) until someone has three distinct cards summing to 15, with Ada going first. a) Prove that Bob does not have a winning strategy. b) Does Ada have a winning strategy? If so, what is it?
- Are there positive integer solutions to $x^3 + y^3 = 9z^3$ other than $(1,2,1)$ and $(2, 1, 1)$?
- Prove that for all non-negative real numbers $a, b, c$ we have $(a^2 + b^2 + c^2)^2 \ge 3(a^3b + b^3 c + c^3 a)$, and determine when equality holds.
- Find all real numbers $r$ such that $n^r$ is an integer for all positive integers $n$.
- Does there exist a positive integer $n$ such that $n, 2n, \ldots, 2015n$ all have the same multiset of nonzero digits?
- Find all ordered triples of non-negative integers $(a,b,c)$ such that $a^2+2b+c$, $b^2+2c+a$, and $c^2+2a+b$ are all perfect squares.
Thursday, June 4, 2015
ACM-ICPC World Finals 2015 Recap
World Finals 2015 Recap
Harvard 3 - Calvin Deng, Johnny Ho, David Liu
We solved 8 problems with a penalty of 1056, good for 19th place.
Order of Solving:
Problem - Penalty (wrong submissions)
A - 00:15
D - 00:39
F - 01:24
I - 01:39 (+1)
C - 02:11 (+1)
L - 02:28
H - 03:30
E - 04:50
Problem A: Amalgamated Artichokes (solved in 15 minutes, 1 submission)
* Solved quickly
* Solved by everyone; Coded by Calvin in 5(?) minutes
* Algorithm: Simple loop, maintain the maximum price encountered so far.
* Notes:
* Was too slow in realizing it was easy
Problem B: Asteroids (not solved, no submissions)
* Notes:
* Guessed that it was ternary search with intersection area,
* Again, unsure if this is correct
* NOTE FOR NEXT YEAR: need triangle intersection / polygon intersection code. (more geometry in general)
Problem C: Catering (solved in 131 minutes, 2 submissions)
* Solved fairly quickly.
* Solved by Johnny / Calvin; Coded by Johnny in 30 mins
* Algorithm: Min-cost max flow
* Notes:
* Could’ve been solved more quickly
* Wasted time not being sure if it was correct
* Wasted time/submission fixing min > max, this should’ve been clear
Problem D: Cutting Cheese (solved in 39 minutes, 1 submission)
* Solved fairly quickly
* Solved by Calvin; Coded by Calvin in 20 mins
* Algorithm: Binary search with volume computations
Problem E: Evolution in Parallel (solved in 290 minutes, 1 submission)
* Solved very slowly
* Solved by Calvin; Coded by Johnny w/ Calvin pair coding in 20 mins
* Algorithm: Greedy Algorithm, with a twist. Maintain three lists: left list, right list, middle list. Sort by length in decreasing order, and add to the middle list when you can; otherwise, add to whichever list fits and move the middle list into the other list (then clear the middle list).
* Notes:
* Didn’t get greedy solution until half an hour or left
* Didn’t realize we could greedy
Problem F: Keyboarding (solved in 84 minutes, 1 submission)
* Solved fairly quickly
* Solved by Calvin; Coded by Johnny in 30 mins
* Algorithm: Simple BFS; the state is (x, y, number of letters typed).
* Notes:
* Wasted time debating solution and not coding completely to specification
* Didn’t realize could move multiple steps at a time, should’ve been clear if we read the problem more carefully
Problem G: Pipe Stream (not solved, no submissions)
* No clue, realized that it was hard early
Problem H: Qanat (solved in 210 minutes, 1 submission)
* Solved by Calvin and David; Coded by Calvin in 15 minutes
* Solved somewhat slowly
* Algorithm: finding formula for each shaft location based on its neighboring shaft locations. More precisely: let $a_0 = 0, a_1, ..., a_n, a_{n+1} = w$ be the locations of the shafts. Then $a_i = (a_{i - 1} + a_{i + 1}) * c$, where I think $c = 1 - h^2 / w^2$? Afterwards, we can first assume $a_1 = 1$ and calculate $a_{n + 1}$, and then scale linearly to fit.
* Notes:
* Took a while to solve, was easy to code though
Problem I: Ship Traffic (solved in 99 minutes, 2 submissions)
* Solved by Johnny fairly quickly
* Coded by Johnny in 20 mins
* Algorithm: Simple interval sorting and merging.
* Waited to solve for no reason because nobody else solved it
* First solve by MIT at 53 minutes, Johnny solved it considerably before then.
* Slightly tripped up by tricky math
* First submission’s bug was stupid, involved flipping a pair and pair
Problem J: Tile Cutting (not solved, no submissions)
* Solved by Johnny / David fairly quickly.
* Algorithm: Basic FFT + Max range queries. Some easy math gives that the number of ways to get an area of $n$ is the sum of $\tau(i)\tau(n - i)$ from $i = 1,..., n-1$, where $\tau(n)$ is the number of divisors of $n$.
* Notes:
* Unfortunately, we did not have FFT code, so we wasted time trying to derive FFT (this was not fruitful).
* NOTE FOR NEXT YEAR: Need to add FFT (probably won't appear again, but this is for the sake of completeness).
Problem K: Tours (not solved, no submissions)
* Notes:
* Didn’t make substantial progress in solving
* Turned out to not be that hard, required splicing on bridges and then isolating nodes that disconnect other nodes
Problem L: Weather Report (solved in 148 minutes, 1 submission)
* Solved by Calvin; Coded by Johnny w/ Calvin pair coding.
* We wasted time testing the problem at the beginning, did not realize discreteness mattered a lot
* Turned out to be Huffman encoding w/ repetitions, solved moderately
* quickly
* Was unsure of time complexity, so we waited after solving it.
* I think it can be shown pretty easily that the program should run in
time (something about bounding the sum of log(probabilities) +
log(frequencies)).
Problem M: Window Manager (not solved in 4 submissions)
* Solved pretty quickly
* Notes:
* Moderately complicated implementation problem
* Johnny wasted large amount of coding time (60+ mins)
* Started Coding M after submitting L, took short breaks to allow E and H to be coded.
* Did not realize reflection/rotation tricks to minimize coding until late
* Did not think carefully about solution before coding
Harvard 3 - Calvin Deng, Johnny Ho, David Liu
We solved 8 problems with a penalty of 1056, good for 19th place.
Order of Solving:
Problem - Penalty (wrong submissions)
A - 00:15
D - 00:39
F - 01:24
I - 01:39 (+1)
C - 02:11 (+1)
L - 02:28
H - 03:30
E - 04:50
Problem A: Amalgamated Artichokes (solved in 15 minutes, 1 submission)
* Solved quickly
* Solved by everyone; Coded by Calvin in 5(?) minutes
* Algorithm: Simple loop, maintain the maximum price encountered so far.
* Notes:
* Was too slow in realizing it was easy
Problem B: Asteroids (not solved, no submissions)
* Notes:
* Guessed that it was ternary search with intersection area,
* Again, unsure if this is correct
* NOTE FOR NEXT YEAR: need triangle intersection / polygon intersection code. (more geometry in general)
Problem C: Catering (solved in 131 minutes, 2 submissions)
* Solved fairly quickly.
* Solved by Johnny / Calvin; Coded by Johnny in 30 mins
* Algorithm: Min-cost max flow
* Notes:
* Could’ve been solved more quickly
* Wasted time not being sure if it was correct
* Wasted time/submission fixing min > max, this should’ve been clear
Problem D: Cutting Cheese (solved in 39 minutes, 1 submission)
* Solved fairly quickly
* Solved by Calvin; Coded by Calvin in 20 mins
* Algorithm: Binary search with volume computations
Problem E: Evolution in Parallel (solved in 290 minutes, 1 submission)
* Solved very slowly
* Solved by Calvin; Coded by Johnny w/ Calvin pair coding in 20 mins
* Algorithm: Greedy Algorithm, with a twist. Maintain three lists: left list, right list, middle list. Sort by length in decreasing order, and add to the middle list when you can; otherwise, add to whichever list fits and move the middle list into the other list (then clear the middle list).
* Notes:
* Didn’t get greedy solution until half an hour or left
* Didn’t realize we could greedy
Problem F: Keyboarding (solved in 84 minutes, 1 submission)
* Solved fairly quickly
* Solved by Calvin; Coded by Johnny in 30 mins
* Algorithm: Simple BFS; the state is (x, y, number of letters typed).
* Notes:
* Wasted time debating solution and not coding completely to specification
* Didn’t realize could move multiple steps at a time, should’ve been clear if we read the problem more carefully
Problem G: Pipe Stream (not solved, no submissions)
* No clue, realized that it was hard early
Problem H: Qanat (solved in 210 minutes, 1 submission)
* Solved by Calvin and David; Coded by Calvin in 15 minutes
* Solved somewhat slowly
* Algorithm: finding formula for each shaft location based on its neighboring shaft locations. More precisely: let $a_0 = 0, a_1, ..., a_n, a_{n+1} = w$ be the locations of the shafts. Then $a_i = (a_{i - 1} + a_{i + 1}) * c$, where I think $c = 1 - h^2 / w^2$? Afterwards, we can first assume $a_1 = 1$ and calculate $a_{n + 1}$, and then scale linearly to fit.
* Notes:
* Took a while to solve, was easy to code though
Problem I: Ship Traffic (solved in 99 minutes, 2 submissions)
* Solved by Johnny fairly quickly
* Coded by Johnny in 20 mins
* Algorithm: Simple interval sorting and merging.
* Waited to solve for no reason because nobody else solved it
* First solve by MIT at 53 minutes, Johnny solved it considerably before then.
* Slightly tripped up by tricky math
* First submission’s bug was stupid, involved flipping a pair
Problem J: Tile Cutting (not solved, no submissions)
* Solved by Johnny / David fairly quickly.
* Algorithm: Basic FFT + Max range queries. Some easy math gives that the number of ways to get an area of $n$ is the sum of $\tau(i)\tau(n - i)$ from $i = 1,..., n-1$, where $\tau(n)$ is the number of divisors of $n$.
* Notes:
* Unfortunately, we did not have FFT code, so we wasted time trying to derive FFT (this was not fruitful).
* NOTE FOR NEXT YEAR: Need to add FFT (probably won't appear again, but this is for the sake of completeness).
Problem K: Tours (not solved, no submissions)
* Notes:
* Didn’t make substantial progress in solving
* Turned out to not be that hard, required splicing on bridges and then isolating nodes that disconnect other nodes
Problem L: Weather Report (solved in 148 minutes, 1 submission)
* Solved by Calvin; Coded by Johnny w/ Calvin pair coding.
* We wasted time testing the problem at the beginning, did not realize discreteness mattered a lot
* Turned out to be Huffman encoding w/ repetitions, solved moderately
* quickly
* Was unsure of time complexity, so we waited after solving it.
* I think it can be shown pretty easily that the program should run in
time (something about bounding the sum of log(probabilities) +
log(frequencies)).
Problem M: Window Manager (not solved in 4 submissions)
* Solved pretty quickly
* Notes:
* Moderately complicated implementation problem
* Johnny wasted large amount of coding time (60+ mins)
* Started Coding M after submitting L, took short breaks to allow E and H to be coded.
* Did not realize reflection/rotation tricks to minimize coding until late
* Did not think carefully about solution before coding
Subscribe to:
Posts
(
Atom
)