Masking in Japan, and Dec 09

Dec. 9th, 2025 09:17 pm
mindstalk: (12KMap)
[personal profile] mindstalk

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

Dec. 9th, 2025 03:11 am
[syndicated profile] terrytao_feed

Posted by Terence Tao

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

For small {n}, one can work this out 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, N/3 + \varepsilon)} 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 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 scores, divided by {10^6} were pretty obviously trying to approximate 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/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, 2/3, 1/2

\displaystyle  2/4, 3/7, 2/5, 3/8, 2/6

\displaystyle  3/9, 4/13, 3/10, 4/14, 3/11, 4/15, 3/12.

which suggested 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, where all blocks are slightly increasing within each block, but the blue blocks are decreasing between each other, and the red blocks are decreasing between each other. The total number of elements is indeed

\displaystyle  |a| \times (k-|a|) + |a+1| \times |a+1| + (k-|a|) \times k = 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 element, 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|

or

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

giving the claim. \Box

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.

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) 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+1} axis-parallel squares of sidelength {d_1,\dots,d_n}, 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

Proof: (Proof of Theorem 4) 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 = (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

Fujisawa 2025-Dec-08

Dec. 9th, 2025 10:53 am
mindstalk: (riboku)
[personal profile] mindstalk

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

siderea: (Default)
[personal profile] siderea
Canonical link: https://siderea.dreamwidth.org/1890011.html

This is part of Understanding Health Insurance





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!
siderea: (Default)
[personal profile] siderea
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

QC RERUN TIME 2025: The Beginning

Dec. 7th, 2025 10:02 pm
[syndicated profile] questionable_content_feed

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

time zones and food

Dec. 7th, 2025 11:34 pm
mindstalk: (food)
[personal profile] mindstalk

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

New travel series begins

Dec. 7th, 2025 10:38 pm
mindstalk: (Default)
[personal profile] mindstalk

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

[syndicated profile] terrytao_feed

Posted by Terence Tao

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.

[syndicated profile] terrytao_feed

Posted by Terence Tao

Wouter van Doorn and I have uploaded to the arXiv our paper “Growth rates of sequences governed by the squarefree properties of its translates“. In this paper we answer a number of questions of Erdős} (Problem 1102 and Problem 1103 on the Erdős problem web site) regarding how quickly a sequence {A = \{a_1 < a_2 < \dots\}} of increasing natural numbers can grow if one constrains its translates {n+A} to interact with the set {\mathcal{SF} = \{1,2,3,5,6,7,10,\dots\}} of squarefree numbers in various ways. For instance, Erdős defined a sequence {A} to have “Property {P}” if each of its translates {n+A} only intersected {\mathcal{SF}} in finitely many points. Erdős believed this to be quite a restrictive condition on {A}, writing “Probably a sequence having property P must increase fairly fast, but I have no results in this direction.”. Perhaps surprisingly, we show that while these sequences must be of density zero, they can in fact grow arbitrary slowly in the sense that one can have {a_j \leq j f(j)} for all sufficiently large {j} and any specified function {f(j)} that tends to infinity as {j \rightarrow \infty}. For instance, one can find a sequence that grows like {O(j \log\log\log j)}. The density zero claim can be proven by a version of the Maier matrix method, and also follows from known moment estimates on the gaps between squarefree numbers; the latter claim is proven by a greedy construction in which one slowly imposes more and more congruence conditions on the sequence to ensure that various translates of the sequence stop being squarefree after a certain point.

Erdős also defined a somewhat complementary property {Q}, which asserts that for infinitely many {n}, all the elements {n+a} of {A} for {a \leq n} are square-free. Since the squarefree numbers themselves have density {6/\pi^2}, it is easy to see that a sequence with property {Q} must have (upper) density at most {6/\pi^2} (because it must be “admissible” in the sense of avoiding one residue class modulo {p^2} for each {p}). Erdős observed that any sufficiently rapidly growing (admissible) sequence would obey property {Q} but beyond that, Erdős writes “I have no precise information about the rate of increase a sequence having property Q must have.”. Our results in this direction may also be surprising: we show that there exist sequences with property {Q} with density exactly {6/\pi^2} (or equivalently, {a_j \sim \frac{\pi^2}{6} j}). This requires a recursive sieve construction, in which one starts with an initial scale {n} and finds a much larger number {n'} such that {n'+a} is squarefree for most of the squarefree numbers {a \leq n'} (and all of the squarefree numbers {a \leq n}). We quantify Erdős’s remark by showing that an (admissible) sequence will necessarily obey property {Q} once it grows significantly faster than {\exp( C j \log j)}, but need not obey this property if it only grows like {\exp(O(j^{1/2} \log^{1/2} j))}. This is achieved through further application of sieve methods.

A third property studied by Erdős is the property of having squarefree sums, so that {a_i + a_j} is squarefree for all {i,j}. Erdős writes, “In fact one can find a sequence which grows exponentially. Must such a sequence really increase so fast? I do not expect that there is such a sequence of polynomial growth.” Here our results are relatively weak: we can construct such a sequence that grows like {\exp(O(j \log j))}, but do not know if this is optimal; the best lower bound we can produce on the growth, coming from the large sieve, is {\gg j^{4/3}}. (Somewhat annoyingly, the precise form of the large sieve inequality we needed was not in the literature, so we have an appendix supplying it.) We suspect that further progress on this problem requires advances in inverse sieve theory.

A weaker property than squarefree sums (but stronger than property {Q}), referred to by Erdős as property {\overline{P}}, asserts that there are infinitely many {n} such that all elements of {n+A} (not just the small ones) are square-free. Here, the situation is close to, but not quite the same, as that for property {Q}; we show that sequences with property {\overline{P}} must have upper density strictly less than {6/\pi^2}, but can have density arbitrarily close to this value.

Finally, we looked at a further question of Erdős on the size of an admissible set {A}. Because the squarefree numbers are admissible, the maximum number {A(x)} of elements of an admissible set {A} up to {x} (OEIS A083544) is at least the number {|{\mathcal SF} \cap [x]|} of squarefree elements up to {x} (A013928). It was observed by Ruzsa that the former sequence is greater than the latter for infinitely many {x}. Erdős asked, “Probably this holds for all large x. It would be of some interest to estimate A(x) as accurately as possible.”

We are able to show

\displaystyle  \frac{\sqrt{x}}{\log x} \ll A(x) - \frac{6}{\pi^2} x \ll x^{4/5},

with the upper bound coming from the large sieve and the lower bound from a probabilistic construction. In contrast, a classical result of Walfisz shows that

\displaystyle  |{\mathcal SF} \cap [x]| - \frac{6}{\pi^2} x \ll x^{1/2} \exp(-c \log^{3/5} x / (\log\log x)^{1/5}).

Together, this implies that Erdős’s conjecture holds {A(x) > |{\mathcal SF} \cap [x]|} for all sufficiently large {x}. Numerically, it appears that in fact this conjecture holds for all {n>17}:

However, we do not currently have enough numerical data for the sequence {A(x)} to completely confirm the conjecture in all cases. This could potentially be a crowdsourced project (similar to the Erdős-Guy-Selfridge project reported on in this previous blog post).

siderea: (Default)
[personal profile] siderea
Canonical link: https://siderea.dreamwidth.org/1888828.html




Hey, Americans and people living in the US going through open enrollment on the state ACA marketplaces who haven't yet enrolled in a plan for 2026!

Just about every state in the union and DC (but not Idaho) proudly touts an end date to open enrollment sometime in January. This year for most states it ends January 15th, but in CA, NJ, NY, RI, and DC, it's January 31st, and here in Massachusetts, it's January 23rd. (Idaho's is December 15th.) [Source]

That sure sounds like the deadline is sometime in January.

No, it kinda isn't.

tl;dr: Just assume if you want insurance to start Jan 1, the deadlines are to enroll by Dec 8 and to pay for the first month by Dec 15. Important deets within. [950 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!
Page generated Dec. 9th, 2025 01:58 pm
Powered by Dreamwidth Studios