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,

\[     \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{}$

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}}$.)

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{}$

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.

1. $\abs{x} = 0$ if and only if $x = 0$.
2. $\abs{xy} = \abs{x}\cdot \abs{y}$.
3. 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{}$

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{}$

Happy 2π Day!

I'm totally not missing the point here...

Problems to Give to Your Enemies

1. 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?
2. Are there positive integer solutions to $x^3 + y^3 = 9z^3$ other than $(1,2,1)$ and $(2, 1, 1)$?
3. 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.
4. Find all real numbers $r$ such that $n^r$ is an integer for all positive integers $n$.
5. Does there exist a positive integer $n$ such that $n, 2n, \ldots, 2015n$ all have the same multiset of nonzero digits?
6. 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.

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

Best-of-7 Series: 3-0 Comebacks

Since it's NBA playoffs season, a common fact that gets thrown around is that no NBA team has ever come back from a 3-0 deficit to win a best-of-7 series. Of course, the NHL and MLB also employ a best-of-7 format (though the MLB only does it for 3 series a year), and both of these leagues have had (at least) one team come back from a 3-0 hole. 

Through fall 2014, NHL teams have performed such a comeback 4 times out of 178 tries (2.25%), NBA teams have come back 0 times out of 110 (0%), and MLB teams (go Red Sox!) have come back 1 time out of 34 (2.94%), for an overall rate of 5 times out of 322 (1.55%). [1]

I thought I'd go through a quick exercise on how likely it is for teams to come back from a 3-0 hole in a best-of-seven series. 

1. Warmup: Team A has a $50$ percent chance of winning any particular game in a best-of-7 series. What is the probability that Team A loses the series, given that it wins the first three games?
2. Team A has a $p$ chance of winning any given game in a best-of-7 series. What is the probability that Team A wins the first three games?
3. Now we don't know anything about $p$, other than the fact that it is drawn from a uniform distribution on $[0,1]$. What is the probability that Team A wins the first three games?
4. Again, $p$ is drawn from a uniform distribution on $[0,1]$. What is the probability that Team A wins the first three games but then loses the next four games?
5. Given that $p$ is drawn from a uniform distribution, what is the conditional probability of Team A losing the series given that it wins the first three games?

If you work these exercises out correctly, you should have gotten the following answers:

1. $\frac{1}{16}$
2. $p^3$
3. $\frac{2}{5}$
4. $\frac{1}{315}$
5. $\frac{1}{126}$

Under this model, the probability of NBA teams going 0-for-110 is $\left(\frac{125}{126}\right)^{110}$, or about 41.6%, so (given this model) it's not too surprising that such a comeback has never happened. 

In reality, NBA/NHL/MLB teams in the playoffs are usually more evenly matched than this model would suggest: for example,  you don't ever see an MLB team being given less than a $\frac{1}{3}$ chance of winning a particular game. Therefore we would expect the distribution for $p$ to be much more concentrated around $\frac{1}{2}$ (compared to the uniform distribution). This in turn should increase the conditional probability of coming back from a 3-0 deficit. The extreme case of this would be when $p$ is fixed at $\frac{1}{2}$, and as we saw there, the condition probability of a 3-0 comeback gets as high as $\frac{1}{16}$.

This model also doesn't account for the home/away split, but my intuition is that that would probably also increase the conditional probability of such a comeback happening. Indeed, the overall comeback rate for 3-0 series is higher than what this simplified model predicts.

In any case, we should be probably be surprised that a 3-0 comeback has never happened in the NBA, but at the same time, don't expect one to happen any time soon.

[1] http://www.whowins.com/tables/up30.html