Reading

Fishing

'That's definitely above the catch-and-release size minimum for planetesimals.' 'I'm going to throw it back anyway.'

QC Rerun Time 2025 #44

http://questionablecontent.net/view.php?comic=5720

It's hard to believe the first Cubetown visit was like 800 friggin' comics ago, holy crap. Time does weird things when you draw a comic every day for 20-odd years. As I recall, at this point I was still trying to figure out if QC would switch solely to focus on Marten and Claire's Cubetown adventures, or if I'd split the focus between Cubetown and Northampton. I ended up doing the latter, which I think was the right choice. Too many fun characters to just leave behind like that! And of course then I immediately added like four new ones, and then Anh basically took over the comic for a year. Is Sam still going through her goth phase? IS it just a phase? ONLY ONE WAY TO FIND OUT (I will do whatever seems funniest at the time)

http://questionablecontent.net/view.php?comic=5720

QC Rerun Time 2025 #3

http://questionablecontent.net/view.php?comic=5719

A Bembo comic! Man I love these. IIRC, the whole idea for Bembo started off on twitter when I went on a bit of a "dumb barbarian but not in the way you'd expect" style of shitposting spree. Then later that year I needed some filler comics for the week between xmas and new year's so I decided to turn some of those posts into actual comics. And then it became a semi-regular thing! They're very fun and I hope to do more in the future. Bembo is obviously heavily indebted to Oglaf, a comic I adore. Go read Oglaf, unless you don't like cartoons with tits and wieners in them I guess.

Every time I see one of these old comics I think "man, remember when QC was about indie rock lol." Also remember when I used to make jokes about the size of Faye's ass but didn't really know how to draw thicker ladies yet so she pretty much looked like every other character, lol.

http://questionablecontent.net/view.php?comic=5719

The Equational Theories Project: Advancing Collaborative Mathematical Research at Scale

Posted by Terence Tao

https://terrytao.wordpress.com/2025/12/09/the-equational-theories-project-advancing-collaborative-mathematical-research-at-scale/

http://terrytao.wordpress.com/?p=15938

Matthew Bolan, Joachim Breitner, Jose Brox, Nicholas Carlini, Mario Carneiro, Floris van Doorn, Martin Dvorak, Andrés Goens, Aaron Hill, Harald Husum, Hernán Ibarra Mejia, Zoltan Kocsis, Bruno Le Floch, Amir Livne Bar-on, Lorenzo Luccioli, Douglas McNeil, Alex Meiburg, Pietro Monticone, Pace P. Nielsen, Emmanuel Osalotioman Osazuwa, Giovanni Paolini, Marco Petracci, Bernhard Reinke, David Renshaw, Marcus Rossel, Cody Roux, Jérémy Scanvic, Shreyas Srinivas, Anand Rao Tadipatri, Vlad Tsyrklevich, Fernando Vaquerizo-Villar, Daniel Weber, Fan Zheng, and I have just uploaded to the arXiv our preprint The Equational Theories Project: Advancing Collaborative Mathematical Research at Scale. This is the final report for the Equational Theories Project, which was proposed in this blog post and also showcased in this subsequent blog post. The aim of this project was to see whether one could collaboratively achieve a large-scale systematic exploration of a mathematical space, which in this case was the implication graph between 4694 equational laws of magmas. A magma is a set ${G}$ equipped with a binary operation ${\diamond: G \times G \rightarrow G}$ (or, equivalently, a ${G \times G}$ multiplication table). An equational law is an equation involving this operation and a number of indeterminate variables. Some examples of equational laws, together with the number that we assigned to that law, include

${E1}$ (Trivial law): ${x = x}$
${E2}$ (Singleton law): ${x = y}$
${E43}$ (Commutative law): ${x \diamond y = y \diamond x}$
${E168}$ (Central groupoid law): ${x = (y \diamond x) \diamond (x \diamond z)}$
${E4512}$ (Associative law): ${x \diamond (y \diamond z) = (x \diamond y) \diamond z}$

Up to relabeling and symmetry, there turn out to be 4694 equational laws that involve at most four invocations of the magma operation ${\diamond}$ ; one can explore them in our “Equation Explorer” tool.

The aim of the project was to work out which of these laws imply which others. For instance, all laws imply the trivial law ${E1}$ , and conversely the singleton law ${E2}$ implies all the others. On the other hand, the commutative law ${E43}$ does not imply the associative law ${E4512}$ (because there exist magmas that are commutative but not associative), nor is the converse true. All in all, there are ${22,028,942}$ implications of this type to settle; most of these are relatively easy and could be resolved in a matter of minutes by an expert in college-level algebra, but prior to this project, it was impractical to actually do so in a manner that could be feasibly verified. Also, this problem is known to become undecidable for sufficiently long equational laws. Nevertheless, we were able to resolve all the implications informally after two months, and have them completely formalized in Lean after a further five months.

After a rather hectic setup process (documented in this personal log), progress came in various waves. Initially, huge swathes of implications could be resolved first by very simple-minded techniques, such as brute-force searching all small finite magmas to refute implications; then, automated theorem provers such as Vampire or Mace4 / Prover9 were deployed to handle a large fraction of the remainder. A few equations had existing literature that allowed for many implications involving them to be determined. This left a core of just under a thousand implications that did not fall to any of the “cheap” methods, and which occupied the bulk of the efforts of the project. As it turns out, all of the remaining implications were negative; the difficulty was to construct explicit magmas that obeyed one law but not another. To do this, we discovered a number of general constructions of magmas that were effective at this task. For instance:

Linear models, in which the carrier ${G}$ was a (commutative or noncommutative) ring and the magma operation took the form ${x \diamond y = ax + by}$ for some coefficients ${a,b}$ , turned out to resolve many cases.
We discovered a new invariant of an equational law, which we call the “twisting semigroup” of that law, which also allowed us to construct further examples of magmas that obeyed one law ${E}$ but not another ${E'}$ , by starting with a base magma ${M}$ that obeyed both laws, taking a Cartesian power ${M^n}$ of that magma, and then “twisting” the magma operation by certain permutations of ${\{1,\dots,n\}}$ designed to preserve ${E}$ but not ${E'}$ .
We developed a theory of “abelian magma extensions”, similar to the notion of an abelian extension of a group, which allowed us to flexibly build new magmas out of old ones in a manner controlled by a certain “magma cohomology group ${H^1_E(G,M)}$ ” which were tractable to compute, and again gave ways to construct magmas that obeyed one law ${E}$ but not another ${E'}$ .
Greedy methods, in which one fills out an infinite multiplication table in a greedy manner (somewhat akin to naively solving a Sudoku puzzle), subject to some rules designed to avoid collisions and maintain a law ${E}$ , as well as some seed entries designed to enforce a counterexample to a separate law ${E'}$ . Despite the apparent complexity of this method, it can be automated in a manner that allowed for many outstanding implications to be refuted.
Smarter ways to utilize automated theorem provers, such as strategically adding in additional axioms to the magma to help narrow the search space, were developed over the course of the project.

Even after applying all these general techniques, though, there were about a dozen particularly difficult implications that resisted even these more powerful methods. Several ad hoc constructions were needed in order to understand the behavior of magmas obeying such equations as E854, E906, E1323, E1516, and E1729, with the latter taking months of effort to finally solve and then formalize.

A variety of GUI interfaces were also developed to facilitate the collaboration (most notably the Equation Explorer tool mentioned above), and several side projects were also created within the project, such as the exploration of the implication graph when the magma was also restricted to be finite. In this case, we resolved all of the ${22,028,942}$ implications except for one (and its dual):

Problem 1 Does the law ${x = y \diamond (x \diamond ((y \diamond x) \diamond y))}$ (E677) imply the law ${x = ((x \diamond x) \diamond x) \diamond x}$ (E255) for finite magmas?

See this blueprint page for some partial results on this problem, which we were unable to resolve even after months of effort.

Interestingly, modern AI tools did not play a major role in this project (but it was largely completed in 2024, before the most recent advanced models became available); while they could resolve many implications, the older “good old-fashioned AI” of automated theorem provers were far cheaper to run and already handled the overwhelming majority of the implications that the advanced AI tools could. But I could imagine that such tools would play a more prominent role in future similar projects.

https://terrytao.wordpress.com/2025/12/09/the-equational-theories-project-advancing-collaborative-mathematical-research-at-scale/

http://terrytao.wordpress.com/?p=15938

Entry tags:

Masking in Japan, and Dec 09

So, you know that Japanese people mask more than Americans or Europeans. But how much more? Some numbers from today: ( Read more... )

So, 40-50% generically outside, and 50-75% on trains. On the "masks and exercise" front, I'd note that many bicyclists have been masked, too.

Further, almost but not entirely all of customer-facing employees have been masked. Train, bus drivers, retail shop employees, the few waiters I've seen. I'd say at least 80% conservatively, 90% likely, maybe not much higher (it takes few outliers to push a ratio away from extremes.) I think Seki said that waiters often aren't, but I dunno.

Now, is this the New Normal after covid? Not necessarily. Japan has been having a bad flu season, huge spike in cases, and a major strain (coming soon to a school or hospital near you) wasn't in the vaccine this year, so I think the government has been urging people to mask again. Also it's winter-ish and some people here may have noticed "masks are like a scarf but better."

( Read more... )

The story of Erdős problem #1026

Posted by Terence Tao

https://terrytao.wordpress.com/2025/12/08/the-story-of-erdos-problem-126/

http://terrytao.wordpress.com/?p=15920

Problem 1026 on the Erdős problem web site recently got solved through an interesting combination of existing literature, online collaboration, and AI tools. The purpose of this blog post is to try to tell the story of this collaboration, and also to supply a complete proof.

The original problem of Erdős, posed in 1975, is rather ambiguous. Erdős starts by recalling his famous theorem with Szekeres that says that given a sequence of ${k^2+1}$ distinct real numbers, one can find a subsequence of length ${k+1}$ which is either increasing or decreasing; and that one cannot improve the ${k^2+1}$ to ${k^2}$ , by considering for instance a sequence of ${k}$ blocks of length ${k}$ , with the numbers in each block decreasing, but the blocks themselves increasing. He also noted a result of Hanani that every sequence of length ${k(k+3)/2}$ can be decomposed into the union of ${k}$ monotone sequences. He then wrote “As far as I know the following question is not yet settled. Let ${x_1,\dots,x_n}$ be a sequence of distinct numbers, determine

$\displaystyle S(x_1,\dots,x_n) = \max \sum_r x_{i_r}$

where the maximum is to be taken over all monotonic sequences ${x_{i_1},\dots,x_{i_m}}$ “.

This problem was added to the Erdős problem site on September 12, 2025, with a note that the problem was rather ambiguous. For any fixed ${n}$ , this is an explicit piecewise linear function of the variables ${x_1,\dots,x_n}$ that could be computed by a simple brute force algorithm, but Erdős was presumably seeking optimal bounds for this quantity under some natural constraint on the ${x_i}$ . The day the problem was posted, Desmond Weisenberg proposed studying the quantity ${c(n)}$ , defined as the largest constant such that

$\displaystyle S(x_1,\dots,x_n) \geq c(n) \sum_{i=1}^n x_i$

for all choices of (distinct) real numbers ${x_1,\dots,x_n}$ . Desmond noted that for this formulation one could assume without loss of generality that the ${x_i}$ were positive, since deleting negative or vanishing ${x_i}$ does not decrease the left-hand side and does not increase the right-hand side. By a limiting argument one could also allow collisions between the ${x_i}$ , so long as one interpreted monotonicity in the weak sense.

Though not stated on the web site, one can formulate this problem in game theoretic terms. Suppose that Alice has a stack of ${N}$ coins for some large ${N}$ . She divides the coins into ${n}$ piles of consisting of ${x_1,\dots,x_n}$ coins each, so that ${\sum_{i=1}^n x_i = N}$ . She then passes the piles to Bob, who is allowed to select a monotone subsequence of the piles (in the weak sense) and keep all the coins in those piles. What is the largest fraction ${c(n)}$ of the coins that Bob can guarantee to keep, regardless of how Alice divides up the coins? (One can work with either a discrete version of this problem where the ${x_i}$ are integers, or a continuous one where the coins can be split fractionally, but in the limit ${N \rightarrow \infty}$ the problems can easily be seen to be equivalent.)

AI-generated images continue to be problematic for a number of reasons, but here is one such image that somewhat manages at least to convey the idea of the game:

For small ${n}$ , one can work out ${c(n)}$ by hand. For ${n=1}$ , clearly ${c(1)=1}$ : Alice has to put all the coins into one pile, which Bob simply takes. Similarly ${c(2)=1}$ : regardless of how Alice divides the coins into two piles, the piles will either be increasing or decreasing, so in either case Bob can take both. The first interesting case is ${n=3}$ . Bob can again always take the two largest piles, guaranteeing himself ${2/3}$ of the coins. On the other hand, if Alice almost divides the coins evenly, for instance into piles ${((1/3 + \varepsilon)N, (1/3-2\varepsilon) N, (1/3+\varepsilon)N)}$ for some small ${\varepsilon>0}$ , then Bob cannot take all three piles as they are non-monotone, and so can only take two of them, allowing Alice to limit the payout fraction to be arbitrarily close to ${2/3}$ . So we conclude that ${c(3)=2/3}$ .

An hour after Desmond’s comment, Stijn Cambie noted (though not in the language I used above) that a similar construction to the one above, in which Alice divides the coins into ${k^2}$ pairs that are almost even, in such a way that the longest monotone sequence is of length ${k}$ , gives the upper bound ${c(k^2) \leq 1/k}$ . It is also easy to see that ${c(n)}$ is a non-increasing function of ${n}$ , so this gives a general bound ${c(n) \leq (1+o(1))/\sqrt{n}}$ . Less than an hour after that, Wouter van Doorn noted that the Hanani result mentioned above gives the lower bound ${c(n) \geq (\frac{1}{\sqrt{2}}-o(1))/\sqrt{n}}$ , and posed the problem of determining the asymptotic limit of ${\sqrt{n} c(n)}$ as ${n \rightarrow \infty}$ , given that this was now known to range between ${1/\sqrt{2}-o(1)}$ and ${1+o(1)}$ . This version was accepted by Thomas Bloom, the moderator of the Erdős problem site, as a valid interpretation of the original problem.

The next day, Stijn computed the first few values of ${c(n)}$ exactly:

$\displaystyle 1, 1, 2/3, 1/2, 1/2, 3/7, 2/5, 3/8, 1/3.$

While the general pattern was not yet clear, this was enough data for Stijn to conjecture that ${c(k^2)=1/k}$ , which would also imply that ${\sqrt{n} c(n) \rightarrow 1}$ as ${n \rightarrow \infty}$ . (EDIT: as later located by an AI deep research tool, this conjecture was also made in Section 12 of this 1980 article of Steele.) Stijn also described the extremizing sequences for this range of ${n}$ , but did not continue the calculation further (a naive computation would take runtime exponential in ${n}$ , due to the large number of possible subsequences to consider).

The problem then lay dormant for almost two months, until December 7, 2025, in which Boris Alexeev, as part of a systematic sweep of the Erdős problems using the AI tool Aristotle, was able to get this tool to autonomously solve this conjecture ${c(k^2)=1/k}$ in the proof assistant language Lean. The proof converted the problem to a rectangle-packing problem.

This was one further addition to a recent sequence of examples where an Erdős problem had been automatically solved in one fashion or another by an AI tool. Like the previous cases, the proof turned out to not be particularly novel. Within an hour, Koishi Chan gave an alternate proof deriving the required bound ${c(k^2) \geq 1/k}$ from the original Erdős-Szekeres theorem by a standard “blow-up” argument which we can give here in the Alice-Bob formulation. Take a large ${M}$ , and replace each pile of ${x_i}$ coins with ${(1+o(1)) M^2 x_i^2}$ new piles, each of size ${(1+o(1)) x_i}$ , chosen so that the longest monotone subsequence in this collection is ${(1+o(1)) M x_i}$ . Among all the new piles, the longest monotone subsequence has length ${(1+o(1)) M S(x_1,\dots,x_n)}$ . Applying Erdős-Szekeres, one concludes the bound

$\displaystyle M S(x_1,\dots,x_n) \geq (1-o(1)) (\sum_{i=1}^{k^2} M^2 x_i^2)^{1/2}$

and on canceling the ${M}$ ‘s, sending ${M \rightarrow \infty}$ , and applying Cauchy-Schwarz, one obtains ${c(k^2) \geq 1/k}$ (in fact the argument gives ${c(n) \geq 1/\sqrt{n}}$ for all ${n}$ ).

Once this proof was found, it was natural to try to see if it had already appeared in the literature. AI deep research tools have successfully located such prior literature in the past, but in this case they did not succeed, and a more “old-fashioned” Google Scholar job turned up some relevant references: a 2016 paper by Tidor, Wang and Yang contained this precise result, citing an earlier paper of Wagner as inspiration for applying “blowup” to the Erdős-Szekeres theorem.

But the story does not end there! Upon reading the above story the next day, I realized that the problem of estimating ${c(n)}$ was a suitable task for AlphaEvolve, which I have used recently as mentioned in this previous post. Specifically, one could task to obtain upper bounds on ${c(n)}$ by directing it to produce real numbers (or integers) ${x_1,\dots,x_n}$ summing up to a fixed sum (I chose ${10^6}$ ) with a small a value of ${S(x_1,\dots,x_n)}$ as possible. After an hour of run time, AlphaEvolve produced the following upper bounds on ${c(n)}$ for ${1 \leq n \leq 16}$ , with some intriguingly structured potential extremizing solutions:

The numerical scores (divided by ${10^6}$ ) were pretty obviously trying to approximate simple rational numbers. There were a variety of ways (including modern AI) to extract the actual rational numbers they were close to, but I searched for a dedicated tool and found this useful little web page of John Cook that did the job:

$\displaystyle 1, 1, 2/3, 1/2, 1/2, 3/7, 2/5, 3/8, 1/3, 1/4.$

$\displaystyle 1/3, 4/13, 3/10, 4/14, 3/11, 4/15, 1/4.$

I could not immediately see the pattern here, but after some trial and error in which I tried to align numerators and denominators, I eventually organized this sequence into a more suggestive form:

$\displaystyle 1,$

$\displaystyle 1/1, \mathbf{2/3}, 1/2,$

$\displaystyle 2/4, \mathbf{3/7}, 2/5, \mathbf{3/8}, 2/6,$

$\displaystyle 3/9, \mathbf{4/13}, 3/10, \mathbf{4/14}, 3/11, \mathbf{4/15}, 3/12.$

This gave a somewhat complicated but predictable conjecture for the values of the sequence ${c(n)}$ . On posting this, Boris found a clean formulation of the conjecture, namely that

$\displaystyle c(k^2 + 2a + 1) = \frac{k}{k^2+a} \ \ \ \ \ (1)$

whenever ${k \geq 1}$ and ${-k \leq a \leq k}$ . After a bit of effort, he also produced an explicit upper bound construction:

Proposition 1 If ${k \geq 1}$ and ${-k \leq a \leq k}$ , then ${c(k^2+2a+1) \leq \frac{k}{k^2+a}}$ .

Proof: Consider a sequence ${x_1,\dots,x_{k^2+2a+1}}$ of numbers clustered around the “red number” ${|a|}$ and “blue number” ${|a+1|}$ , consisting of ${|a|}$ blocks of ${k-|a|}$ “blue” numbers, followed by ${|a+1|}$ blocks of ${|a+1|}$ “red” numbers, and then ${k-|a|}$ further blocks of ${k}$ “blue” numbers. When ${a \geq 0}$ , one should take all blocks to be slightly decreasing within each block, but the blue blocks should be are increasing between each other, and the red blocks should also be increasing between each other. When ${a < 0}$ , all of these orderings should be reversed. The total number of elements is indeed

$\displaystyle |a| \times (k-|a|) + |a+1| \times |a+1| + (k-|a|) \times k$

$\displaystyle = k^2 + 2a + 1$

and the total sum is close to

$\displaystyle |a| \times (k-|a|) \times |a+1| + |a+1| \times |a+1| \times |a|$

$+ (k-|a|) \times k \times |a+1| = (k^2 + a) |a+1|.$

With this setup, one can check that any monotone sequence consists either of at most ${|a+1|}$ red elements and at most ${k-|a|}$ blue elements, or no red elements and at most ${k}$ blue elements, in either case giving a monotone sum that is bounded by either

$\displaystyle |a+1| \times |a| + (k-|a|) \times |a+1| = k |a+1|$

$\displaystyle 0 + k \times |a+1| = k |a+1|,$

giving the claim. $\Box$

Here is a figure illustrating the above construction in the ${a \geq 0}$ case (obtained after starting with a ChatGPT-provided file and then manually fixing a number of placement issues):

Here is a plot of $1/c(n)$ (produced by ChatGPT Pro), showing that it is basically a piecewise linear approximation to the square root function:

Shortly afterwards, Lawrence Wu clarified the connection between this problem and a square packing problem, which was also due to Erdős (Problem 106). Let ${f(n)}$ be the least number such that, whenever one packs ${n}$ squares of sidelength ${d_1,\dots,d_n}$ into a square of sidelength ${D}$ , with all sides parallel to the coordinate axes, one has

$\displaystyle \sum_{i=1}^n d_i \leq f(n) D.$

Proposition 2 For any ${n}$ , one has
$\displaystyle c(n) \geq \frac{1}{f(n)}.$

Proof: Given ${x_1,\dots,x_n}$ and ${1 \leq i \leq n}$ , let ${S_i}$ be the maximal sum over all increasing subsequences ending in ${x_i}$ , and ${T_i}$ be the maximal sum over all decreasing subsequences ending in ${x_i}$ . For ${i < j}$ , we have either ${S_j \geq S_i + x_j}$ (if ${x_j \geq x_i}$ ) or ${T_j \geq T_i + x_j}$ (if ${x_j \leq x_i}$ ). In particular, the squares ${(S_i-x_i, T_i-x_i)}$ and ${(S_j-x_j, T_j-x_j)}$ are disjoint. These squares pack into the square ${[0, S(x_1,\dots,x_n)]^2}$ , so by definition of ${f}$ , we have

$\displaystyle \sum_{i=1}^n x_i \leq f(n) S(x_1,\dots,x_n),$

and the claim follows. $\Box$

This idea of using packing to prove Erdős-Szekeres type results goes back to a 1959 paper of Seidenberg, although it was a discrete rectangle-packing argument that was not phrased in such an elegantly geometric form. It is possible that Aristotle was “aware” of the Seidenberg argument via its training data, as it had incorporated a version of this argument in its proof.

Here is an illustration of the above argument using the AlphaEvolve-provided example

$\displaystyle[99998, 99997, 116305, 117032, 116304,$

$\displaystyle 58370, 83179, 117030, 92705, 99080]$

for $n=10$ to convert it to a square packing (image produced by ChatGPT Pro):

At this point, Lawrence performed another AI deep research search, this time successfully locating a paper from just last year by Baek, Koizumi, and Ueoro, where they show that

Theorem 3 For any ${k \geq 1}$ , one has
$\displaystyle f(k^2+1) \leq k$

which, when combined with a previous argument of Praton, implies

Theorem 4 For any ${k \geq 1}$ and ${c \in {\bf Z}}$ with ${k^2+2c+1 \geq 1}$ , one has
$\displaystyle f(k^2+2c+1) \leq k + \frac{c}{k}.$

This proves the conjecture!

There just remained the issue of putting everything together. I did feed all of the above information into a large language model, which was able to produce a coherent proof of (1) assuming the results of Baek-Koizumi-Ueoro and Praton. Of course, LLM outputs are prone to hallucination, so it would be preferable to formalize that argument in Lean, but this looks quite doable with current tools, and I expect this to be accomplished shortly. But I was also able to reproduce the arguments of Baek-Koizumi-Ueoro and Praton, which I include below for completeness.

Proof: (Proof of Theorem 3, adapted from Baek-Koizumi-Ueoro) We can normalize ${D=k}$ . It then suffices to show that if we pack the length ${k}$ torus ${({\bf Z}/k{\bf Z})^2}$ by ${k^2+1}$ axis-parallel squares of sidelength ${d_1,\dots,d_{k^2+1}}$ , then

$\displaystyle \sum_{i=1}^{k^2+1} d_i \leq k^2.$

Pick ${x_0, y_0 \in {\bf R}/k{\bf Z}}$ . Then we have a ${k \times k}$ grid

$\displaystyle (x_0 + {\bf Z}) \times (y_0 + {\bf Z}) \pmod {k{\bf Z}^2}$

inside the torus. The ${i^{th}}$ square, when restricted to this grid, becomes a discrete rectangle ${A_{i,x_0} \times B_{i,y_0}}$ for some finite sets ${A_{i,x_0}, B_{i,y_0}}$ with

$\displaystyle |\# A_{i,x_0} -\# B_{i,y_0}| \leq 1. \ \ \ \ \ (2)$

By the packing condition, we have

$\displaystyle \sum_{i=1}^{k^2+1} \# A_{i,x_0} \# B_{i,y_0} \leq k^2.$

From (2) we have

$\displaystyle (\# A_{i,x_0} - 1) (\# B_{i,y_0} - 1) \geq 0$

hence

$\displaystyle \# A_{i,x_0} \# B_{i,y_0} \geq \# A_{i,x_0} + \# B_{i,y_0} - 1.$

Inserting this bound and rearranging, we conclude that

$\displaystyle \sum_{i=1}^{k^2+1} \# A_{i,x_0} + \sum_{i=1}^{k^2+1} \# B_{i,y_0} \leq 2k^2 + 1.$

Taking the supremum over ${x_0,y_0}$ we conclude that

$\displaystyle \sup_{x_0} \sum_{i=1}^{k^2+1} \# A_{i,x_0} + \sup_{y_0} \sum_{i=1}^{k^2+1} \# B_{i,y_0} \leq 2k^2 + 1$

so by the pigeonhole principle one of the summands is at most ${k^2}$ . Let’s say it is the former, thus

$\displaystyle \sup_{x_0} \sum_{i=1}^{k^2+1} \# A_{i,x_0} \leq k^2.$

In particular, the average value of ${\sum_{i=1}^{k^2+1} \# A_{i,x_0}}$ is at most ${k^2}$ . But this can be computed to be ${\sum_{i=1}^{k^2+1} d_i}$ , giving the claim. Similarly if it is the other sum. $\Box$

UPDATE: Actually, the above argument also proves Theorem 4 with only minor modifications. Nevertheless, we give the original derivation of Theorem 4 using the embedding argument of Praton below for sake of completeness.

Proof: (Proof of Theorem 4, adapted from Praton) We write ${c = \epsilon |c|}$ with ${\epsilon = \pm 1}$ . We can rescale so that the square one is packing into is ${[0,k]^2}$ . Thus, we pack ${k^2+2\varepsilon |c|+1}$ squares of sidelength ${d_1,\dots,d_{k^2+2\varepsilon |c|+1}}$ into ${[0,k]^2}$ , and our task is to show that

$\displaystyle \sum_{i=1}^{k^2+2\varepsilon|c|+1} d_i \leq k^2 + \varepsilon |c|.$

We pick a large natural number ${N}$ (in particular, larger than ${k}$ ), and consider the three nested squares

$\displaystyle [0,k]^2 \subset [0,N]^2 \subset [0,N + |c| \frac{N}{N-\varepsilon}]^2.$

We can pack ${[0,N]^2 \backslash [0,k]^2}$ by ${N^2-k^2}$ unit squares. We can similarly pack

$\displaystyle [0,N + |c| \frac{N}{N-\varepsilon}]^2 \backslash [0,N]^2$

$\displaystyle =[0, \frac{N}{N-\varepsilon} (N+|c|-\varepsilon)]^2 \backslash [0, \frac{N}{N-\varepsilon} (N-\varepsilon)]^2$

into ${(N+|c|-\varepsilon)^2 - (N-\varepsilon)^2}$ squares of sidelength ${\frac{N}{N-\varepsilon}}$ . All in all, this produces

$\displaystyle k^2+2\varepsilon |c|+1 + N^2-k^2 + (N+|c|-\varepsilon)^2 - (N-\varepsilon)^2$

$\displaystyle = (N+|c|)^2 + 1$

squares, of total length

$\displaystyle (\sum_{i=1}^{k^2+2\varepsilon |c|+1} d_i) +(N^2-k^2) + ((N+|c|-\varepsilon)^2 - (N-\varepsilon)^2) \frac{N}{N-\varepsilon}.$

Applying Theorem 3, we conclude that

$\displaystyle (\sum_{i=1}^{k^2+2\varepsilon |c|+1} d_i) +(N^2-k^2)$

$\displaystyle + ((N+|c|-\varepsilon)^2 - (N-\varepsilon)^2) \frac{N}{N-\varepsilon} \leq (N+|c|) (N + |c| \frac{N}{N-\varepsilon}).$

The right-hand side is

$\displaystyle N^2 + 2|c| N + |c|^2 + \varepsilon |c| + O(1/N)$

and the left-hand side similarly evaluates to

$\displaystyle (\sum_{i=1}^{k^2+2c+1} d_i) + N^2 -k^2 + 2|c| N + |c|^2 + O(1/N)$

and so we simplify to

$\displaystyle \sum_{i=1}^{k^2+2\varepsilon |c|+1} d_i \leq k^2 + \varepsilon |c| + O(1/N).$

Sending ${N \rightarrow \infty}$ , we obtain the claim. $\Box$

One striking feature of this story for me is how important it was to have a diverse set of people, literature, and tools to attack this problem. To be able to state and prove the precise formula for ${c(n)}$ required multiple observations, including some version of the following:

The sequence can be numerically computed as a sequence of rational numbers.
When appropriately normalized and arranged, visible patterns in this sequence appear that allow one to conjecture the form of the sequence.
This problem is a weighted version of the Erdős-Szekeres theorem.
Among the many proofs of the Erdős-Szekeres theorem is the proof of Seidenberg in 1959, which can be interpreted as a discrete rectangle packing argument.
This problem can be reinterpreted as a continuous square packing problem, and in fact is closely related to (a generalized axis-parallel form of) Erdős problem 106, which concerns such packings.
The axis-parallel form of Erdős problem 106 was recently solved by Baek-Koizumi-Ueoro.
The paper of Praton shows that Erdős Problem 106 implies the generalized version needed for this problem. This implication specializes to the axis-parallel case.

It was only through the combined efforts of all the contributors and their tools that all these key inputs were able to be assembled within 48 hours. It seems plausible that a more traditional effort involving just one or two mathematicians and simpler programming and literature search tools may eventually have been able to put all these pieces together, but I believe this process would have taken much longer (on the order of weeks or even months).

Another key ingredient was the balanced AI policy on the Erdős problem website, which encourages disclosed AI usage while strongly discouraging undisclosed use. To quote from that policy: “Comments prepared with the assistance of AI are permitted, provided (a) this is disclosed, (b) the contents (including mathematics, code, numerical data, and the existence of relevant sources) have been carefully checked and verified by the user themselves without the assistance of AI, and (c) the comment is not unreasonably long.”

https://terrytao.wordpress.com/2025/12/08/the-story-of-erdos-problem-126/

http://terrytao.wordpress.com/?p=15920

Hyperacute Interdynamics

https://xkcd.com/3178/

Our models fall apart where the three theories overlap; we're unable to predict what happens when a nanometer-sized squirrel eats a grapefruit with the mass of the sun.

https://xkcd.com/3178/

Entry tags:

Fujisawa 2025-Dec-08

So, yesterday: I worried I'd gotten a germ after all, since I woke up with a slight sore throat and almost-congestion. There was an alternative explanation, "sleeping in a cold dry room", but who knows. I went out for a walk and ended up out for 3 hours, which suggests good health, though I was doing easy pace. ( Read more... )

Entry tags:

Understanding Health Insurance: A Health Plan is a Contract [US, healthcare, Patreon]

Canonical link: https://siderea.dreamwidth.org/1890011.html

This is part of Understanding Health Insurance

Introduction
A Health Plan is a Contract ⇐ You are here

Health Insurance is a Contract

What we call health insurance is a contract. When you get health insurance, you (or somebody on your behalf) are agreeing to a contract with a health insurance company – a contract where they agree to do certain things for you in exchange for money. So a health insurance plan is a contract between the insurance company and the customer (you).

For simplicity, I will use the term health plan to mean the actual contract – the specific health insurance product – you get from a health insurance company. (It sounds less weird than saying "an insurance" and is shorter to type than "a health insurance plan".)

One of the things this clarifies is that one health insurance company can have a bunch of different contracts (health plans) to sell. This is the same as how you may have more than one internet company that could sell you an internet connection to your home, and each of those internet companies might have several different package deals they offer with different prices and terms. In exactly that way, there are multiple different health insurance companies, and they each can sell multiple different health plans with different prices and terms.

( Read more... [7,130 words] )

This post brought to you by the 220 readers who funded my writing it – thank you all so much! You can see who they are at my Patreon page. If you're not one of them, and would be willing to chip in so I can write more things like this, please do so there.

Please leave comments on the Comment Catcher comment, instead of the main body of the post – unless you are commenting to get a copy of the post sent to you in email through the notification system, then go ahead and comment on it directly. Thanks!

Entry tags:

Understanding Health Insurance: Introduction [healthcare, US, Patreon]

Canonical link: https://siderea.dreamwidth.org/1889543.html

Preface: I had hoped to get this out in a more timely manner, but was hindered by technical difficulties with my arms, which have now been resolved. This is a serial about health insurance in the US from the consumer's point of view, of potential use for people still dealing with open enrollment, which we are coming up on the end of imminently. For everyone else dealing with the US health insurance system, such as it is, perhaps it will be useful to you in the future.

Understanding Health Insurance:
Introduction

Health insurance in the US is hard to understand. It just is. If you find it confusing and bewildering, as well as infuriating, it's not just you.

I think that one of the reasons it's hard to understand has to do with how definitions work.

Part of the reason why health insurance is so confusing is all the insurance industry jargon that is used. Unfortunately, there's no way around that jargon. We all are stuck having to learn what all these strange terms mean. So helpful people try to explain that jargon. They try to help by giving definitions.

But definitions are like leaves: you need a trunk and some branches to hang them on, or they just swirl around in bewildering clouds and eventually settle in indecipherable piles.

There are several big ideas that provide the trunk and branches of understanding health insurance. If you have those ideas, the jargon becomes a lot easier to understand, and then insurance itself becomes a lot easier to understand.

So in this series, I am going to explain some of those big ideas, and then use them to explain how health insurance is organized.

This unorthodox introduction to health insurance is for beginners to health insurance in the US, and anyone who still feels like a beginner after bouncing off the bureaucratic nightmare that is our so-called health care system in the US. It's for anyone who is new to being an health insurance shopper in the US, or feels their understanding is uncertain. Maybe you just got your first job and are being asked to pick a health plan from several offered. Maybe you have always had insurance from an employer and are shopping on your state marketplace for the first time. Maybe you have always gotten insurance through your parents and spouse, and had no say in it, but do now. This introduction assumes you are coming in cold, a complete beginner knowing nothing about health insurance or what any of the health insurance industry jargon even is.

Please note! This series is mostly about commercial insurance products: the kinds that you buy with money. Included in that are the kind of health insurance people buy for themselves on the state ACA marketplaces and also the kind of health insurance people get from their employers as a "bene". It may (I am honestly not sure) also include Medicare Advantage plans.

The things this series explains do not necessarily also describe Medicaid or bare Medicare, or Tricare or any other government run insurance program, though if you are on such an insurance plan this may still be helpful to you. Typically government-run plans have fewer moving parts with fewer choices, so fewer jargon terms even matter to them. Similarly, this may be less useful for subsidized plans on the state ACA marketplaces. It depends on the state. Some states do things differently for differently subsidized plans.

But all these different kinds of government-provided health insurance still use some insurance industry jargon for commercial insurance, if only to tell you what they don't have or do. So this post may be useful to you because understanding how insurance typically works may still prove helpful in understanding what the government is up to. Understanding what the assumptions are of regular commercial insurance will hopefully clarify the terms even government plans use to describe themselves. Just realize that if you have a plan the government in some sense is running, things may be different – including maybe very different – for you.

On to the first important idea: Health Insurance is a Contract.

Understanding Health Insurance

Introduction
Health Insurance is a Contract

QC RERUN TIME 2025: The Beginning

http://questionablecontent.net/view.php?comic=5716

lmao that the first comic to pop up when I hit the random button on my site was Faye saying "why's there always gotta be new people"

Looking back at this year, I feel like Anh basically took over the comic? It's wild how it's always the unexpected ones who have the most juice. No offense to Ayo, who is also plenty juicy and I also love writing. But Anh's a couple orders of magnitude more of a mess. But THIS comic is about AYO! Who is a delightful little idiot and I can't wait to do more with. OKAY THANKS I LOVE YOU ALL BYE

http://questionablecontent.net/view.php?comic=5716

Signs

https://www.oglaf.com/signs/

Entry tags:

time zones and food

Gonna take a while to get used to these time zones differences again. I realized in the shower that as I was preparing to go to bed before Monday, for most of my friends, Sunday morning was just beginning. Also, that's probably why Oglaf hasn't updated yet -- it's Sunday! My webcomics schedule is in confusion. ( Read more... )

Entry tags:

New travel series begins

After three years in friendly Very Cheap Rent houses, I'm back to nomadic life. After bouncing around Philly a few times to get things sorted, I'm now in Tokyo, because (a) Japan is cool and (b) old family of friend is old, tick-tock tick-tock. If you want to follow along, well, keep checking in for the travel2025 tag. Some random observations to start: ( Read more... )

Chessboard Alignment

https://xkcd.com/3177/

Luckily, the range is limited by the fact that the square boundary lines follow great circles.

https://xkcd.com/3177/

WHEEL SMASHING LORD 5-156

Posted by Abbadon

https://killsixbilliondemons.com/comic/wheel-smashing-lord-5-156/

https://killsixbilliondemons.com/?post_type=comic&p=4148

Mercenary Soul

https://killsixbilliondemons.com/comic/wheel-smashing-lord-5-156/

https://killsixbilliondemons.com/?post_type=comic&p=4148

Inverted Catenaries

https://xkcd.com/3176/

Some tires are marketed as 'all-shape tires,' but if driven in a climate with both inverted catenary falls and triangle falls, they wear out really fast.

https://xkcd.com/3176/

They're Just Like Us

http://questionablecontent.net/view.php?comic=5715

just a regular girl

http://questionablecontent.net/view.php?comic=5715

Sex Ed With Faye

http://questionablecontent.net/view.php?comic=5714

Sexual Edward

http://questionablecontent.net/view.php?comic=5714

Quantitative correlations and some problems on prime factors of consecutive integers

Posted by Terence Tao

https://terrytao.wordpress.com/2025/12/01/quantitative-correlations-and-some-problems-on-prime-factors-of-consecutive-integers/

http://terrytao.wordpress.com/?p=15892

Joni Teravainen and I have uploaded to the arXiv our paper “Quantitative correlations and some problems on prime factors of consecutive integers“. This paper applies modern analytic number theory tools – most notably, the Maynard sieve and the recent correlation estimates for bounded multiplicative functions of Pilatte – to resolve (either partially or fully) some old problems of Erdős, Strauss, Pomerance, Sárközy, and Hildebrand, mostly regarding the prime counting function

$\displaystyle \omega(n) := \sum_{p|n} 1$

and its relatives. The famous Hardy–Ramanujan and Erdős–Kac laws tell us that asymptotically for ${n \sim x}$ , ${\omega(n)}$ should behave like a gaussian random variable with mean and variance both close to ${\log\log x}$ ; but the question of the joint distribution of consecutive values such as ${\omega(n), \omega(n+1)}$ is still only partially understood. Aside from some lower order correlations at small primes (arising from such observations as the fact that precisely one of ${n,n+1}$ will be divisible by ${2}$ ), the expectation is that such consecutive values behave like independent random variables. As an indication of the state of the art, it was recently shown by Charamaras and Richter that any bounded observables ${f(\omega(n))}$ , ${g(\omega(n+1))}$ will be asymptotically decorrelated in the limit ${n \rightarrow \infty}$ if one performs a logarithmic statistical averaging. Roughly speaking, this confirms the independence heuristic at the scale ${\sqrt{\log\log x}}$ of the standard deviation, but does not resolve finer-grained information, such as precisely estimating the probability of the event ${\omega(n)=\omega(n+1)}$ .

Our first result, answering a question of Erdős, shows that there are infinitely many ${n}$ for which one has the bound

$\displaystyle \omega(n+k) \ll k$

for all ${k \geq 1}$ . For ${k \gg \log\log n}$ , such a bound is already to be expected (though not completely universal) from the Hardy–Ramanujan law; the main difficulty is thus with the short shifts ${k = o(\log\log n)}$ . If one only had to demonstrate this type of bound for a bounded number of ${k}$ , then this type of result is well within standard sieve theory methods, which can make any bounded number of shifts ${n+k}$ “almost prime” in the sense that ${\omega(n+k)}$ becomes bounded. Thus the problem is that the “sieve dimension” ${\sim \log\log n}$ grows (slowly) with ${n}$ . When writing about this problem in 1980, Erdős and Graham write “we just know too little about sieves to be able to handle such a question (“we” here means not just us but the collective wisdom (?) of our poor struggling human race)”.

However, with the advent of the Maynard sieve (also sometimes referred to as the Maynard–Tao sieve), it turns out to be possible to sieve for the conditions ${\omega(n+k) \ll k}$ for all ${k = o(\log\log n)}$ simultaneously (roughly speaking, by sieving out any ${n}$ for which ${n+k}$ is divisible by a prime ${p \ll x^{1/\exp(Ck)}}$ for a large ${C}$ ), and then performing a moment calculation analogous to the standard proof (due to Turán) of the Hardy–Ramanujan law, but weighted by the Maynard sieve. (In order to get good enough convergence, one needs to control fourth moments as well as second moments, but these are standard, if somewhat tedious, calculations).

Our second result, which answers a separate question of Erdős, establishes that the quantity

$\displaystyle \sum_n \frac{\omega(n)}{2^n} = 0.5169428\dots$

is irrational; this had recently been established by Pratt under the assumption of the prime tuples conjecture, but we are able to establish this result unconditoinally. The binary expansion of this number is of course closely related to the distribution of ${\omega}$ , but in view of the Hardy–Ramanujan law, the ${n^{th}}$ digit of this number is influenced by about ${\log\log\log n}$ nearby values of ${\omega}$ , which is too many correlations for current technology to handle. However, it is possible to do some “Gowers norm” type calculations to decouple things to the point where pairwise correlation information is sufficient. To see this, suppose for contradiction that this number was a rational ${a/q}$ , thus

$\displaystyle q \sum_n \frac{\omega(n)}{2^n} = 0 \hbox{ mod } 1.$

Multiplying by ${2^n}$ , we obtain some relations between shifts ${\omega(n+h)}$ :

$\displaystyle q \sum_{h=1}^\infty \frac{\omega(n+h)}{2^h} = 0 \hbox{ mod } 1.$

Using the additive nature of ${\omega}$ , one then also gets similar relations on arithmetic progressions, for many ${n}$ and ${p}$ :

$\displaystyle q \sum_{h=1}^\infty \frac{\omega(n+ph)}{2^h} = 0 \hbox{ mod } 1.$

Taking alternating sums of this sort of identity for various ${n}$ and ${p}$ (in analogy to how averages involving arithmetic progressions can be related to Gowers norm-type expressions over cubes), one can eventually arrive eliminate the contribution of small ${H}$ , and arrive at an identity of the form

$\displaystyle q \sum_{h=1}^\infty \frac{\sum_{\epsilon \in \{0,1\}^K} (-1)^{|\epsilon|} \omega(n + r_{\epsilon,h+K})}{2^{h+K}} = 0 \hbox{ mod } 1 \ \ \ \ \ (1)$

for many ${n}$ , where ${K}$ is a parameter (we eventually take ${K \sim \log\log\log\log n}$ ) and ${r_{\epsilon,h+K}}$ are various shifts that we will not write out explicitly here. This looks like quite a messy expression; however, one can adapt proofs of the Erdős–Kac law and show that, as long as one ignores the contribution of really large prime factors (of order ${\gg n^{1/10}}$ , say) to the ${\omega(n + r_{\epsilon,h+K})}$ , that this sort of sum behaves like a gaussian, and in particular once one can show a suitable local limit theorem, one can contradict (1). The contribution of the large prime factors does cause a problem though, as a naive application of the triangle inequality bounds this contribution by ${O(1)}$ , which is an error that overwhelms the information provided by (1). To resolve this we have to adapt the pairwise correlation estimates of Pilatte mentioned earlier to demonstrate that the these contributions are in fact ${o(1)}$ . Here it is important that the error estimates of Pilatte are quite strong (of order ${O(\log^{-c} n)}$ ); previous correlation estimates of this type (such as those used in this earlier paper with Joni) turn out to be too weak for this argument to close.

Our final result concerns the asymptotic behavior of the density

$\displaystyle \frac{1}{x} \{n \leq x: \omega(n+1) = \omega(n)\}$

(we also address similar questions for ${\Omega(n+1)=\Omega(n)}$ and ${\tau(n+1)=\tau(n)}$ ). Heuristic arguments led Erdős, Pomerance, and Sárközy to conjecture that this quantity was asymptotically ${\frac{1}{2\sqrt{\pi \log\log x}}}$ . They were able to establish an upper bound of ${O(1/\log\log x)}$ , while Hildebrand obtained a lower bound of ${\gg 1/(\log\log x)^3}$ , due to Hildebrand. Here, we obtain the asymptotic for almost all ${x}$ (the limitation here is the standard one, which is that the current technology on pairwise correlation estimates either requires logarithmic averaging, or is restricted to almost all scales rather than all scales). Roughly speaking, the idea is to use the circle method to rewrite the above density in terms of expressions

$\displaystyle \frac{1}{x} \sum_{n \leq x} e(\alpha \omega(n+1)) e(-\alpha \omega(n))$

for various frequencies ${\alpha}$ , use the estimates of Pilatte to handle the minor arc ${\alpha}$ , and convert the major arc contribution back into physical space (in which ${\omega(n+1)}$ and ${\omega(n)}$ are now permitted to differ by a large amount) and use more traditional sieve theoretic methods to estimate the result.

https://terrytao.wordpress.com/2025/12/01/quantitative-correlations-and-some-problems-on-prime-factors-of-consecutive-integers/

http://terrytao.wordpress.com/?p=15892