iiinova — where your digital self keeps evolving

Thomas Steinke @stein.ke · 22/07/2026

xkcd.com/2385/ openai.com/index/huggin...

339150

Thomas Steinke @stein.ke · 16/07/2026

What does “tokens per second per request” mean?? www.theatlantic.com/technology/2...

480

Thomas Steinke @stein.ke · 02/07/2026

Oh yeah I remember that. I remember showing up at the conference venue to present my poster in swim gear, still wet from snorkeling. 😅

https://x.com/trustworthy_ml/status/1685168877444173824

120

Thomas Steinke @stein.ke · 02/07/2026

I’m attending COLT 2026 in San Diego. You can see the beach from the conference venue; not sure if that’s a good thing. 🤔 learningtheory.org/colt2026/

2170

Thomas Steinke @stein.ke · 27/05/2026

A handsome red bike, abandoned. By a busy road, outside my home. Locked to a tow away sign. What happened to its owner? Not even a thief has come for it. What will the HOA do? I see it daily and wonder.

A red bike in good condition locked to a signpost bearing a tow away sign, with a busy road in the background.

230

Thomas Steinke @stein.ke · 16/05/2026

Here's an example of a "hallucinated" citation from a decade ago (i.e. pre-LLMs). The same bad citation appeared in multiple papers. I eventually traced the source to Google Scholar (and it's now fixed).

[2] Marcus Hardt and Jonathan Ullman. Preventing false discovery in interactive data analysis is
hard. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages
454–463. IEEE, 2014.

From: https://arxiv.org/abs/1510.03349

[11] Marcus Hardt and Jonathan Ullman. Preventing
false discovery in interactive data analysis is hard.
In Foundations of Computer Science (FOCS), 2014
IEEE 55th Annual Symposium on, pages 454–463.
IEEE, 2014.

From: https://proceedings.mlr.press/v51/russo16.pdf

[19]
Marcus Hardt and Jonathan Ullman. 2014. Preventing false discovery in interactive data analysis is hard. In IEEE Symposium on Foundations of Computer Science (FOCS). 454--463.

From: https://dl.acm.org/doi/10.1145/3139550.3139556

Article (Correct)

Preventing False Discovery in Interactive Data Analysis Is Hard
Authors: Moritz Hardt, Jonathan Ullman
FOCS '14: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science
Pages 454 - 463
https://doi.org/10.1109/FOCS.2014.55
Published: 18 October 2014 Publication History

From: https://dl.acm.org/doi/10.1109/FOCS.2014.55

272

Thomas Steinke @stein.ke · 12/03/2026

Some people are still debating whether or not LLMs are "useful," so let's stake out one clear use case: LLMs are useful for translating between languages. That includes translating between natural languages (e.g. Spanish to English) and, more recently, to formal languages (e.g. English to Python).

Screenshot of bsky post with author's identity not shown. [I'm not trying to pile on.]

Sure, LLMs are useful for:
1. Fraud
2. Plagiarism
3. Cognitive off-loading
Which of those use-cases are you promoting?

3:59pm March 10 2026
51 reposts, 14 quotes, 257 likes, 6 saves

3332

Thomas Steinke @stein.ke · 07/02/2026

I like spotting license plates from interesting states. This one was notably interesting.

Picture of a car license plate with the number obscured. The plate says.
CHAHTA SIA HOKE!
In God We Trust
Choctaw Nation of OKLAHOMA

041

Thomas Steinke @stein.ke · 31/01/2026

Which is the best option for returning nothing?

Screenshot of Amazon app listing return options.
Whole foods
Staples
Kohl's
UPS
Etc.

100

Thomas Steinke @stein.ke · 31/01/2026

Amazon sent me an empty/broken package. I'm trying to get my money back, but there's no explicit option for this. I may have to "return" the item by sending an empty package back.

Photo of a green label on top of a white USPS label on a brown package.
The green label says the following.

ATTENTION CUSTOMER
* RECEIVED UNSEALED
* RECEIVED DAMAGED
* RECEIVED WITHOUT CONTENTS

There is a handwritten "B 1/30/26" on the green label.

100

Thomas Steinke @stein.ke · 17/01/2026

The cost of living is out of control: A bag of ice costs $4 and my local supermarket is out of stock. This is why we need Greenland.

Screenshot showing search results for "ice". The first result is a 5lb bag for $3.99 and is shown as out of stock.

0100

Thomas Steinke @stein.ke · 31/12/2025

TIL that the etymology of "California" is plausibly related to "Caliphate".

https://en.wikipedia.org/wiki/Etymology_of_California

2100

Thomas Steinke @stein.ke · 29/12/2025

Imagine you are a trained next word prediction model and you see this.

https://en.wikipedia.org/wiki/Ted_Jorgensen

0443

Thomas Steinke @stein.ke · 09/10/2025

IMHO, the best analog to the AI bubble is the dotcom bubble. Yes, the internet proved to be economically transformative, but there was still a bubble. Companies made a lot of money in the end, but it wasn't necessarily the ones that people expected -- e.g., see CISCO:

Plot of CISCO's stock price from 1990-2025 showing huge growth around 2000 before dropping and slowly growing again.

050

Thomas Steinke @stein.ke · 13/08/2025

🤦🤦🤦 this is not how two factor identification works 🤦🤦🤦🤦

[Screenshot of an app]
Code Verification
Call customer service at 1-866-4220306 (outside the U.S. call 1-210-677-0065) to retrieve your One-time identification Code .

0221

Thomas Steinke @stein.ke · 27/06/2025

Doing linear algebra in finite fields is fun because numerical instability doesn't exist. Alas, library support is limited, so you may find yourself writing your own Gaussian elimination.

def modinv(a, p):
"""Computes inverse of a modulo p i.e. returns b such that (a*b)%p==1"""
u, v = a % p, p
x, y, w, z = 1, 0, 0, 1 # maintain ax+py==u and aw+pz==v
while u != 0: # extended Euclidean algorithm
q, r = v // u, v % u
x, y, w, z = w-qx, z-qy, x, y
u, v = r, u
if v != 1: return None # not invertible
return w % p

def modmatrixinverse(A, p):
"""Computes matrix inverse of A modulo p i.e. returns B s.t. A@B%p==I"""
A = numpy.array(A, dtype=int)
m, n = A.shape
assert m == n, "matrix must be square"
B = numpy.eye(n, dtype=int) # = nxn identity matrix
for i in range(n): # Gaussian elimination
b, j = None, i-1
while b is None:
j += 1
if j >= n: return None # not invertible
b = modinv(A[j,i], p)
if j > i: # swap rows i and j
A[j,:], A[i,:] = A[i,:], A[j,:]
B[j,:], B[i,:] = B[i,:], B[j,:]
A[i,:] = (A[i,:] * b) % p # divide A[i,:] by A[i,i]
B[i,:] = (B[i,:] * b) % p
for j in range(n): # zero out the rest of column i
if j != i:
B[j,:] = (B[j,:] - B[i,:] * A[j,i]) % p
A[j,:] = (A[j,:] - A[i,:] * A[j,i]) % p
return B

4483

Thomas Steinke @stein.ke · 22/05/2025

What's the full acronym then? 🤔

Picture of an Amazon delivery truck with the following written the side.

The 'P' in ASAP stands for Prime.

150

Thomas Steinke @stein.ke · 14/05/2025

I'm a fan of the Jensen proof. It generalizes to prove Hölder's inequality:

$\textbf{H\"older's inequality from Jensen's inequality:} \noindent Let $x,y\in\mathbb{R}^d$ be arbitrary. Let $p,q \in (1,\infty)$ satisfy $\frac1p+\frac1q=1$. Without loss of generality, assume $x_i \ne 0$ for all $i \in [d]$. Note that $v \mapsto |v|^p$ is convex. For $i \in [d]$, define $u_i = |x_i|^q/\|x\|_q^q$ and $v_i = x_iy_i/|x_i|^q$. By Jensen's inequality, \[\left|\frac{\sum_i x_i y_i}{\|x\|_q^q}\right|^p = \left|\sum_i u_i v_i\right|^p \le \sum_i u_i |v_i|^p = \frac{\sum_i |x_i|^{q+p-pq}|y_i|^p}{\|x\|_q^q} = \frac{\|y\|_p^p}{\|x\|_q^q}, \] which rearranges to \[\left|\sum_i x_i y_i\right| \le \|x\|_q \cdot \|y\|_p.\]$

010

Thomas Steinke @stein.ke · 14/05/2025

Three proofs of Cauchy-Schwarz. ⟨x,y⟩ ≤ ∥x∥ ∥y∥ Are there any others you know of?

$\textbf{Fact:} $\forall u, v \ge 0 ~~~ \inf_{t>0} t \cdot u + \frac1t \cdot v = 2\sqrt{uv}$ \begin{proof} Assume $uv>0$; otherwise the proof is trivial. Let $f(t) = t \cdot u + \frac1t \cdot v$. Then $f'(t) = u-v/t^2$. Now $f'(t)=0 \iff t = \sqrt{v/u}$. Thus $\inf_{t>0} f(t) = f(\sqrt{v/u}) = 2\sqrt{uv}$. \end{proof} Let $x,y\in\mathbb{R}^d$. Then \begin{align*} \sum_i x_i y_i &\le \frac12 \sum_i 2\sqrt{x_i^2 \cdot y_i^2} \tag{absolute value} \\ &= \frac12 \sum_i \inf_{t_i>0} t_i \cdot x_i^2 + \frac{1}{t_i} \cdot y_i^2 \\ &\le \frac12 \inf_{t>0} \sum_i t \cdot x_i^2 + \frac1t \cdot y_i^2\\ &= \frac12 \inf_{t>0} t \cdot \|x\|^2 + \frac1t \cdot \|y\|^2\\ &= \sqrt{ \|x\|^2 \cdot \|y\|^2 } = \|x\| \cdot \|y\|. \end{align*}$ $\textbf{Jensen's inequality:} \noindent Let $x,y\in\mathbb{R}^d$ be arbitrary. Without loss of generality, assume $x_i \ne 0$ for all $i \in [d]$. For $i \in [d]$, define $p_i = x_i^2/\|x\|^2$ and $v_i = y_i/x_i$. By Jensen's inequality, \[\left(\frac{\sum_i x_i y_i}{\|x\|^2}\right)^2 = \left(\sum_i p_i v_i\right)^2 \le \sum_i p_i v_i^2 = \frac{\sum_i y_i^2}{\|x\|^2}, \] which rearranges to \[\sum_i x_i y_i \le \|x\| \cdot \|y\|.\]$ $\textbf{Sum of squares:} \noindent Let $x,y\in\mathbb{R}^d$. For all $\alpha,\beta>0$, \[0 \le \| \alpha x - \beta y \|^2 = \alpha^2\|x\|^2 + \beta^2\|y\|^2 -2\alpha\beta\langle x , y \rangle\] and, hence, \[\langle x , y \rangle \le \frac{\alpha}{2\beta}\|x\|^2 + \frac{\beta}{2\alpha}\|y\|^2.\] If $\|x\|=0$ or $\|y\|=0$, clearly $\langle x , y \rangle = 0$. Otherwise, set $\alpha=\|y\|$ and $\beta=\|x\|$ to obtain \[\langle x , y \rangle \le \frac{\|y\|}{2\|x\|}\|x\|^2 + \frac{\|x\|}{2\|y\|}\|y\|^2 = \|x\| \cdot \| y \|.\]$

5282

Thomas Steinke @stein.ke · 07/05/2025

Suppose X,Y,Z,W are independent standard Gaussians. Then X·Y+W·Z has a standard Laplace distribution. Similarly, Z·√(X^2+Y^2) has a standard Laplace distribution

LaTeX source: https://pastebin.com/zL7rVVSN

1180

Thomas Steinke @stein.ke · 27/04/2025

As an application of this, we get to prove concentrated differential privacy for the restricted Gaussian mechanism. E.g. if you have a bounded query and add Gaussian noise, you can condition the noisy output to also be bounded without any loss in privacy parameters. 😁

LaTeX source for all 3 pages: https://pastebin.com/W6AtEwJ1

050

Thomas Steinke @stein.ke · 27/04/2025

Here's an application using the Log Sobolev Inequality for strongly log-concave distributions to bound KL divergence which can thus be converted to a bound on Rényi divergence.

150

Thomas Steinke @stein.ke · 26/04/2025

You can bound Rényi divergences in terms of KL divergences for tilted distributions. This is useful e.g. for Gaussians, where tilting just corresponds to shifting the distribution.

LaTeX source: https://pastebin.com/m9RwBcCi

4403

Thomas Steinke @stein.ke · 19/04/2025

There are also rod cells in your retina. In principle these give you a 4th dimension for perceiving colour. But they are for peripheral & night vision, so we don't perceive a 4th color dimension. 🤷

Source: https://commons.wikimedia.org/wiki/File:Cone-absorbance-en.svg

140

Thomas Steinke @stein.ke · 19/04/2025

Colours correspond to infinite-dimensional vectors, since there are infinitely many wavelengths of light. But humans can only perceive a three-dimensional projection of colour (red, green, & blue). What's interesting is that it's *not* an orthogonal projection. Here's a plot of the basis vectors.

Source: https://commons.wikimedia.org/wiki/File:XYZ_color_matching_functions,_CIE_1931_and_Stockman_%26_Sharpe_2006.jpg

1464

Thomas Steinke @stein.ke · 19/04/2025

Taking α→1 gives a triangle inequality for KL divergence. This can also be proved using my favourite lemma. 😁

$Full LaTeX source: https://pastebin.com/mA6KjUJs \begin{proposition}[Triangle-like inequality for KL divergence]\label{prop:kl-triangle} Let $P$, $R$, and $Q$ be probability distributions with $P$ being absolutely continuous with respect to $R$ and $R$ being absolutely conotinuous with respect to $Q$. Let $\kappa \in (1,\infty)$. Then \[ \dr{\text{KL}}{P}{Q} \le \frac{\kappa}{\kappa-1} \dr{\text{KL}}{P}{R} + \dr{\kappa}{R}{Q}, \] where $\dr{\text{KL}}{P}{Q} := \ex{X \gets P}{\log(P(X)/Q(X)}$ denotes the KL divergence and\\$\dr{\kappa}{R}{Q} = \frac{1}{\kappa-1} \log \ex{X \gets R}{(R(X)/Q(X))^{\kappa-1}}$ denotes the R\'enyi divergence of order $\kappa$. \end{proposition}$

052

Thomas Steinke @stein.ke · 19/04/2025

Renyi divergences satisfy a triangle inequality (with an extra multiplier). The proof boils down to Holder's inequality.

$Screenshot of Lemma 5.2 and its proof from page 18 of https://arxiv.org/abs/1605.02065 Lemma 5.2 (Triangle-like Inequality for Renyi Divergence). Let P, Q, and R be probability distributions. Then D_a(P||Q) <= \frac{ka}{ka-1} D_{(ka-1)/(k-1)}(P||R) + D_{ka}(R||Q) for all k,a in (1,inf).$

2152

Thomas Steinke @stein.ke · 04/04/2025

Here's a very simple calculation showing that adding a bit of randomization can make numerical integration better even in the one-dimensional setting.

LaTeX source: https://pastebin.com/1sGyGLBT

2541

Thomas Steinke @stein.ke · 29/03/2025

Rather than a uniform bound (a.k.a. Kolmogorov–Smirnov distance), we can also get a universal multiplicative bound. This is tighter in the tails of the distribution.

LaTeX source: https://pastebin.com/C1nT9sEt (page 3)

120

Thomas Steinke @stein.ke · 29/03/2025

The DKW inequality states that, given i.i.d. samples from a univariate distribution, with high probability the empirical CDF is *uniformly* close to the true CDF. The uniform guarantee is as tight as the pointwise guarantee. (Alas I couldn't get this proof down to 1 page. 😅 )

LaTeX source: https://pastebin.com/C1nT9sEt

3262

Thomas Steinke @stein.ke · 27/03/2025

The quotient rule for higher derivatives is not as messy as I feared. 😅 And the matrix is lower-triangular, so it's easy to invert.

$LaTeX source: https://pastebin.com/qtw8DPh8 \begin{lemma}[Quotient Rule for Higher Derivatives] ~\\ Let $h(x) := \frac{f(x)}{g(x)}$ with $g(x) \ne 0$. Then, %$h'(x) = \frac{f'(x)g(x)-f(x)g'(x)}{g(x)^2}$. More generally, for all $n \in \mathbb{N}$, \[ \left(\begin{array}{c} h(x) \\ h'(x) \\ h''(x) \\ h'''(x) \\ \vdots \\ h^{(k)}(x) \\ \vdots \\ h^{(n-1)}(x) \end{array}\right) = \left(\begin{array}{ccccc} g(x) & 0 & 0 & \cdots & 0 \\ g'(x) & g(x) & 0 & \cdots & 0 \\ g''(x) & 2 g'(x) & g(x) & \cdots & 0 \\ g'''(x) & 3 g''(x) & 3 g'(x) & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & 0 \\ g^{(k)}(x) & {k \choose 1} g^{(k-1)}(x) & {k \choose 2} g^{(k-2)}(x) & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & 0 \\ g^{(n-1)}(x) & {n-1 \choose 1} g^{(n-2)}(x) & {n-1 \choose 2} g^{(n-3)}(x) & \cdots & g(x) \end{array}\right)^{-1} \left(\begin{array}{c} f(x) \\ f'(x) \\ f''(x) \\ f'''(x) \\ \vdots \\ f^{(k)}(x) \\ \vdots \\ f^{(n-1)}(x) \end{array}\right) . \] \end{lemma}$

070

Thomas Steinke @stein.ke · 26/03/2025

L.J. Mordell effectively republished the formula in 1933. This paper is available. In it he laments that his 1920 paper is not well known. doi.org/10.1007/BF02...

Screenshot of old paper with following text

324 L.J. Mordell.
in finite terms when n is an integer. The general integral or particular cases
have also been considered by Lerch 1, Hardy ~, Ramanujan 3, van der Corput ~ and
myself. My results which included the complete evaluation of the general integral, were found in September 1918 and published in I92O in volume 48 of the
Quarterly Journal. The paper is not well known and has even escaped the
notice of the editors of the Fortschritte. Further, it is not easily accessible
outside of Great Britain. It seems in view of the interest aroused by Siegel's
paper that it might be desirable to give a more accessible and fuller account of
the iutegral, and the considerations leading to it and the results deduced from
it.

140

Thomas Steinke @stein.ke · 26/03/2025

This formula is known as the Mordell integral. If you try looking up Mordell's original paper from 1920, you get nothing: 🙃

creenshot from Google Scholar with the followng text. But no link to the paper.

[CITATION] The value of the definite integral∫∞−∞ eat2+ bt ect+ d dt
LJ Mordell - Quarterly J. of Math, 1920
Save Cite Cited by 35 Related articles

120

Thomas Steinke @stein.ke · 26/03/2025

I don't know how someone came up with this crazy formula for the mean of a logit-Normal, but I'm glad they did. It converges extremely fast. en.wikipedia.org/wiki/Logit-n...

$\begin{proposition}[Mean of Logit-Normal Distribution] For all $\mu\in\mathbb{R}$ and all $\sigma>0$, \begin{align*} &\ex{X \gets \mathcal{N}(\mu,\sigma^2)}{\frac{1}{1+e^{-X}}} = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^\infty \frac{1}{1+e^{-(\mu+\sigma x)}} e^{-x^2/2} \mathrm{d}x \\ &= \frac12 + \frac{\sum_{n=1}^\infty e^{-\sigma^2n^2/2} \sinh(n\mu)\tanh(n\sigma^2/2) + \frac{2\pi}{\sigma^2} e^{-(2n-1)^2\pi^2/2\sigma^2} \frac{\sin((2n-1)\pi\mu/\sigma^2)}{\sinh((2n-1)\pi^2/\sigma^2)}}{1 + 2 \sum_{m=1}^\infty e^{-\sigma^2m^2/2} \cosh(m\mu)} \end{align*} \end{proposition}$

3280

Thomas Steinke @stein.ke · 25/03/2025

Integration is to differentiation as NP is to P.

$\begin{theorem} For all $c>1$, \[\frac{1}{2\pi} \int_{-\pi}^{\pi} \frac{1}{c+\sin(\theta)} \mathrm{d} \theta = \frac{1}{\sqrt{c^2-1}}.\] \end{theorem} \begin{proof} Clearly \[\frac{\mathrm{d}}{\mathrm{d}\theta} \left[ \frac{2}{\sqrt{c^2-1}} \tan^{-1}\left(\frac{1 + c \tan (\theta/2)}{\sqrt{c^2-1}}\right) \right] = \frac{1}{c+\sin(\theta)}.\] The result now follows from the fundamental theorem of calculus. \end{proof}$

0101

Thomas Steinke @stein.ke · 24/03/2025

Upper bounds like this are particularly useful, e.g., if you need to bound the expectation E[log(1+exp(X))]. This bound is a reformulation of Proposition 4.1 of arxiv.org/abs/1901.09188 or Equation 1.3 in doi.org/10.1214/ECP....

Proposition 4.1 in
https://arxiv.org/pdf/1901.09188.pdf#page=12

010

Thomas Steinke @stein.ke · 24/03/2025

This is known as the Kearns-Saul inequality, which improves Hoeffding's lemma. It gives the optimal constant (independent of a) coefficient for the quadratic term. It matches the Taylor series in constant & linear terms. See how the upper bound compares to the 2nd-order Taylor series:

Graph showing log(1+exp(x)), second order taylor series at x=2, & corresponding quadratic upper bound.

Graph showing log(1+exp(x)), second order taylor series at x=-3, & corresponding quadratic upper bound.

Graph showing log(1+exp(x)), second order taylor series at x=1, & corresponding quadratic upper bound.

$Quadratic upper bound: \[\log(1+e^x) \le \log(1+e^a) + \frac{x-a}{1+e^{-a}} + \frac{(e^a-1) \cdot (x-a)^2}{4 \cdot a \cdot (e^a+1)}.\] Second-order Taylor series: \[\log(1+e^x) \approx \log(1+e^a) + \frac{x-a}{1+e^{-a}} + \frac{ (x-a)^2}{2 \cdot (e^a+2+e^{-a})}.\]$

210

Thomas Steinke @stein.ke · 24/03/2025

The "softplus" function log(1+exp(x)) arises surprisingly often for me. It's a smooth approximation to a ReLU i.e. max{0,x}. Specifically, max{0,x} <= log(1+exp(x)) <= max{0,x} + exp(-|x|). Sometimes it's useful to have a polynomial upper bound, and this is the best quadratic:

$For all $a,x \in \mathbb{R}$ with $a \ne 0$, we have \[\log(1+e^x) \le \log(1+e^a) + \frac{x-a}{1+e^{-a}} + \frac{(e^a-1) \cdot (x-a)^2}{4 \cdot a \cdot (e^a+1)}.\] Furthermore, for each $a$, this is the smallest quadratic upper bound on $\log(1+e^x)$ satisfying equality at $x=a$.$

3221

Thomas Steinke @stein.ke · 22/03/2025

The largest known prime number is 2¹³⁶²⁷⁹⁸⁴¹−1 For Mersenne primes m=2ⁿ-1, the Lucas-Lehmer primality test runs in Õ(n²) time *deterministically*. The dominant operation is squaring n-bit integers n times; naïve multiplication would require O(n³) time. For n>10⁸ that still takes a long time...

def is_mersenne_prime(n):
"""Checks if 2^n-1 is prime (returns True) or composite (False)."""
assert isinstance(n, int) and n >= 2
if n == 2: return True # Special case
# First check n is prime by trial division
k = 2
while k * k <= n:
if n % k == 0: return False
k = k + 1
# Lucas-Lehmer primality test for m=2^n-1
m = 2**n - 1
s = 4
for _ in range(n - 2):
s = ( (s * s) - 2 ) % m
return (s == 0)

050

Thomas Steinke @stein.ke · 22/03/2025

Primality testing is an interesting topic. General-purpose primality tests for n-bit numbers also take Õ(n²) time. But the algorithm is randomized and has a nonzero probability of giving a false positive. Deterministic algorithms take Õ(n⁶) time.

Python code for Miller-Rabin primality test:
https://pastebin.com/NCFijWDZ

4171

Thomas Steinke @stein.ke · 08/03/2025

Prime numbers are plentiful. Here's a simple proof that the number of primes ≤n is ≥Ω(n / log n), which is a (small) constant factor from optimal.

$LaTeX source: https://pastebin.com/BeABGVqE Let $\pi(n)$ denote the number of prime numbers $\le n$. The prime number theorem states that \begin{equation} \lim_{n \to \infty} \frac{~\pi(n)~}{~\frac{n}{\log n}~} = 1. \label{eq:primes} \end{equation} Here's a weaker, one-sided (but non-asymptotic) result with a simpler proof: \begin{theorem}\label{thm:primes} For all $n \in \mathbb{N}$, we have $\pi(n) \ge \frac{n-2}{\log_2 n}$. \end{theorem} \begin{lemma}\label{lem:lcm} Define $\mathsf{lcm}(n) := \min\{m \in \mathbb{N} : \forall k \in [n] ~ \frac{m}{k} \in \mathbb{N}\}$ to be the least common multiple of $[n] := \{1,2,\cdots,n\}$. Then $\mathsf{lcm}(n) \ge 2^{n-2}$ for all $n \in \mathbb{N}$. \end{lemma}$

5331

Thomas Steinke @stein.ke · 05/03/2025

Pet peeve: Websites where the "Sign up" button is more prominent than the "Log in" button. (Looking at you, overleaf.com 👀) But this is next level:

Screenshot from https://www.submittable.com/ showing a plain "Sign In" link next to a bright orange, circled "Talk to Sales" link.

2190

Thomas Steinke @stein.ke · 02/02/2025

It's a well-known fact™ that estimating the mean of a Bernoulli distribution from n independent samples must have mean squared error Ω(1/n). But it's surprisingly difficult to find a clean proof or citation for this fact. Here's my attempt. 😅

$LaTeX source: https://pastebin.com/tA8BLbaw \begin{proposition} Let $f : \{0,1\}^n \to \mathbb{R}$ be an estimator with the following property. \[\forall p \in [0,1] ~~ \ex{X_1 \cdots X_n \gets \mathsf{Bernoulli}(p)}{(f(X)-p)^2} \le \alpha^2.\] Then $\alpha^2 \ge \frac{1}{6(n+2)}$. \end{proposition}$

11516

Thomas Steinke @stein.ke · 02/02/2025

I was randomly reminded of this amazing propaganda poster from the Great Leap Forward. (If you don't see what's wrong with the image, ask your favourite AI what's the difference between rowing and paddling.)

Photo of a poster depicting a large dragon boat with sails and rowers (facing forwards) and a small shipwreck in the corner. The crew of the dragon boat look full of vigor, while the shipwrecked crew look on wearily.

The caption is in Chinese but translates to "The great leap forward in the east worries the west."

191

Thomas Steinke @stein.ke · 25/01/2025

On the difference between precision and accuracy: The prescribed dose is 7.1mL, so the pharmacy gave us a large syringe and told us to measure 7mL with it and a small syringe to measure 0.1mL.

3160