Jared Duker Lichtman: Primitive sets and von Mangoldt chains: Erdős #1196 and beyond (NTWS 297)

primitive set. So in other words, uh the natural density must uh may not always exist. It may fluctuate, but the limb soup is always less than a half and the limb imp is always equal to zero. And for this lower bound actually uh had proven the stronger result in 1935 that the following series of 1 / n log n for n ranging in the primitive set a is uniformly bounded by some constant uh uniformly over any primitive set a. And uh after uh Erdosh we call uh this series the the Erdish sum of of a. And uh so we're presented now with a situation where we have an infinite family of uh series that are all bounded by some constant and uh as such it's natural to ask what is the maximum what is the value of this uh largest constant and uh Erdosh went on to conjecture that this uh constant was actually attained by uh the series for the primes. So in other words that the aish primitive second vector is that uh the air sum for the primes is larger or is at least as large as the air sum for any uh other primitive set. And so in particular if you wanted to compute uh the error sum for the primes this is 1 over two log 2 plus 1 over 3 log 3 plus 1 over 5 log 5 and so on. So this infinite series over primes one term for each prime and um through some uh kind of clever numerical integration uh work of Enri Cohen actually shows that uh this series is about 1.636 and so the conjecture of Erdish just said that for any primitive set uh its err sum is at most this constant about 1.636 636. And so initially uh back in the 90s uh Erdos and Jeang had proven that the air sum of any primitive set was at almost 1.84 and in 2019 uh Carl Pomerance and I uh improved this bound somewhat to uh e to the gamma which is about 1.78. uh and here gamma is the oiler macaroni constant and in the study of this problem one might uh naively approach this conjecture by directly computing these partial sums up to x and then letting x go to infinity um in fact if you tried to do this for this series of the primes uh this turns out to be quite difficult to compute um and work of uh Cohen and others had had come up with another way to interpret this series um and in particular particular uh the tail of the series uh conver uh kind of decays like one over log x which is extremely slow and even worse there are examples of primitive sets a all integers larger than x for which um the kind of bulk mass of the series uh is concentrated in the tail and so in particular the sum of this tail is approximately one or asmtotically one um and so in particular particular this approach of just truncating uh a series at x is actually inadequate for for this kind of problem and uh a more kind of local approach towards uh conjecture uh that turns out to be more natural is to split up uh the set a according to the smallest prime factor of of the integer. So in other words for every prime p we'll denote a subp to be the subset of integers in our set a uh that have smallest prime factor p and uh one can introduce the notion of an error strong prime p if um the error sum for the subset a subp is at most uh just the singleton f of p uh in other words 1 over p log p for all primitive sets A and so in other words this is uh saying that the singleton set uh has the maximum error sum among all primitive sets a subp. So all uh primitive sets whose uh elements have smallest prime factor equal to p. And the nice thing about this problem is is that if each prime is a strong, one can kind of recover the full conjecture quite uh immediately as uh by splitting up our uh set a into subsets a subp. Uh then our error sum over a is equal to uh the sum over primes p of a uh the error sum of a sub p and uh error strong property means that we have this pointwise upper bound at each subset uh by f of p and if we sum over the primes uh we recover in turn the error sum of all primes. So this is a very nice and natural uh approach to to to study this problem. And uh in 2022 uh as uh I guess ancient history by now um uh I worked uh uh on this problem and uh resolved uh both the original conjecture uh as well as uh the odd form of uh these this local refinement of the problem. So in particular for any primitive set a and any odd prime bigger than two we have that f of uh a subp so the subset of integers uh in in our set uh whose smallest prime factor is equal to p is at most of the singleton uh f of p and uh in particular from the methods uh it remained an open question whether uh the first prime p equals 2 is er wrong and in other words this is asking whether or not uh the error sum of a primitive set of even numbers is at most 1 over2 log 2. So it's a very concrete question and uh as often happens in number theory the methods uh that were used uh in order to prove the original problem kind of broke down in this uh uh setting of just even numbers and as often case in that happens the the odd primes kind of have maybe of a different behavior and uh for some reason uh uh for that reason some people say that uh the the prime two is the oddest of them all. Um, and with that as context, as kind of background, I wanted to now talk about uh this uh problem of air 1196. Um, and uh, of course, if anyone has questions throughout, just uh, feel free to um, message them in the chat and um, I think Philip said he'll he'll uh, uh, let us know. Um so the problem is a asmtoic version of the primitive set conjecture and in 1966 Erdog and Simi were interested in looking at primitive sets uh of integers all bigger than x and understanding how the air sum behaves in the limit as x tends to infinity. So this is a very different kind of problem uh in in in nature um because you know for example with the primes uh if you truncate x uh and look at just the tail the tail is converging to to zero one over log x. So this is um uh really looking at these sets whose uh bulk kind of concentrates in the tail and uh so in particular uh not having some random value of 1.636 636 we actually have uh a value of one plus plus plus plus little 01. So a really remarkable uh uh conjecture and uh in particular the proof methods uh working on the original primitive set conjecture uh enabled the following upper bound of e to the gamma times uh pi over4 and this uh numerically is about 1.399 so about 1.4 four and the goal is to bring down uh this value from 1.4 down down down to one. Uh and it's also uh maybe worth kind of reflecting on what the significance of this uh uh conjecture is. Um so if we recall uh from our first slide that the set of k almost primes so the numbers with exactly k prime factors is a primitive set and the smallest such uh k almost prime is exactly the prime power 2 to the k. So in particular all the numbers are at least 2 to the k and as k t tends to infinity we have a collection of very large numbers they're all bigger than uh 2 to the k and uh in particular uh with work of uh with gordki and and modic wang in 2023 we prove that in fact this family um of the kos primes has sum tending to one as as k goes to infinity. So in particular the this limit of one uh is a witness for a subf family in this uh limb soup uh question of Erdos suckers and samarid in air 1196. Um so we know for a fact um that the limit this limb soup must lie be some number lying between 1 and 1.4 four and therefore their conjecture um is the assertion that the lower bound is actually sharp and that one gets an equality uh of one in this limb soup and so in other words that uh the kos primes become optimal for this problem as k tends to infinity. So this is a an optimizing uh uh sub panel. So this was uh uh ancient history and uh now we come to uh this here where to my surprise uh this problem of air dish 1196 was solved in April. So in particular uh on April 13th an amateur mathematician uh named Leman Price posted on uh the air problems website that GPT 5.4 4 Pro claims a solution to this problem and had a link to a PDF that was about uh four pages long um uh where it said it ran uh autonomously on the problem for about uh 80 minutes about an hour and a half and produced raw output that uh generated a plausible solution. However, on the face of it, the the draft was really quite rough and I think the the pro style was uh as typical of these uh AI generated uh files was was quite poor and and hard to decipher. But, uh the draft was only you know four pages long. So, it was it was quite short. Um and I am uh care about this problem uh quite a bit. So, I was motivated to at least identify uh what what was going on here. And at the face of it, I was quite skeptical of of of this problem uh being four pages of a proof. But after an hour of maybe deciphering it, digesting and rewriting, I was actually satisfied that the the draft uh was correct. Um and um in retrospect in most respects this uh this solution follows uh spiritually the same kind of approach as previous works in the literature um by which one constructs a measure uh to interpret the anatomy of integers of of elements of A. Um however there were some kind of striking elements in particular the unexpected use of these certain weights B of X uh B subX uh defined uh in terms of the vangu function. So uh just to recall for for those who who forgot. So recall that the the uh students in number theory uh that appear a bit odd to to just looking at it for the first time. So it's def your integer is a prime power and uh if n is a prime power p of the k then it's just equal to to log p. And uh so this might be seeming like an arbitrary choice of a definition. But as we know using the logarithmic derivative uh this turns out to be a very central uh definition connecting the primes and the reman zeta function. Um and in particular we have a very kind of nice key identity um for the vonled function which encodes unique factorization of an integer n into prime powers. So in particular the sum over uh divisor uh of n uh lambda of q once you sum over divisor is equal to log n and um so this was uh uh you know the the von mangle functions is this classic function um however it's very analytic in nature and hadn't really been connected to the to this problem before so all prior works uh uh of others going back to the original work in the 1930s had all been based on a much more kind of probabilistic uh idea. So namely one wanted to relate uh an interest sum to uh a probability measure using the Merren's prime product theorem. So namely that this uh term 1 / n log n is approximately a constant over n times this burton's product of 1 - 1 over p for primes uh up to the largest prime factor of n. So one can actually put in n but uh it's convenient to write it this way and the constant um in Merton's theorem turns out to be e to the gamma the same the same constant. And so this is a very I would say nice conceptual move. Um going from analysis which can be quite technical to these nice probabilities which have the beautiful feature that they always sum to some uh value at most one. And so this is the core uh driver of the proof. And so we can actually explain uh Erdish's original argument from 1935 using using this maybe uh explained in modern language. So we can give a sketch right here just in one slide. So we're going to show that the error sum of any primitive set is uh uniformly bounded. And for simplicity uh we can just assume all the integers are are large here. So what we're going to do is uh express our error sum of 1 / a log a and if we denote by p of a to be the largest prime factor of our set uh this is uh a simple upper bound of 1 / a log p of a and if we now apply merrens theorem this is uh upper bounded by a constant uh time 1 / a uh times this merrenton product of primes up to P of A of 1 - 1 over P. And once we have it in this form, you might say why why have we done this this kind of seemingly arbitrary step? But the the key point is that we can now recognize this expression uh 1 / A times this MERS product as equaling the natural density of a subset of of integers. Namely, consider L sub A to be the family of all multiples of A of the form B * A where all the primes in B are at least as large as the largest prime factor of A. So in other words, we're considering multiples of A where all the primes that are small are in A and all the large primes are in B. And uh that is to say we've now uh expressed an upper bound in terms of a sum of these natural densities of L sub A. And by uh a short argument uh one can show so up to this point we've used nothing no information at all about our set A. But uh here we use the key property that our set is primitive. And in particular by a short argument this tells us that uh these uh sets of multiples L sub A are pair-wise disjoint. And so now uh our upper bound of a sum of densities uh of disjoint uh sets now becomes the density of a union of these disjoint sets. And in particular this union is some set uh which we denote by L sub capital A. And in particular its density is at most one and just using this nice nice property. So in particular uh we get this constant upper bound um uh a as desired and this is essentially everything that goes into Eric's proof. Um it's really kind of a a very elegant uh idea and um one can actually uh uh if one likes one one can rephrase uh this argument in in the language uh of uh submarov chains these so-called merin submarov chains uh hitting this primitive uh um being hit by this primitive set a um and uh also when we apply uh the uh Merren's theorem with this and we get this uh uh less than less than this is kind of hiding under the under the hood. We get a numerical factor that we pay as a cost. So this this factor e to the gamma about and so in my uh uh original proof on the air primure uh I really had to deal with this numerical cost and uh gain a savings back in some way and uh in that case I uh studied the relationship between um uh the s the relative sizes between uh the integer and its uh second largest prime factor and this gives a certain ratio of logarithms um After uh studying um the anatomy of integers of each of the in uh numbers in our set, we we showed that this ratio of uh actually gives some savings in in all cases. Um and that turns out to be just enough to uh we get the savings of pi over4. Um this this turns out to be just enough uh to get to get the the ball rolling. Um and this would also suggest in the study of air 1196 that one could iterate this idea in order to study uh the so-called joint distribution maybe the first j primes p1 of n up to pj ofn and so by studying this joint distribution um this actually uh approach works extremely well in the special case that we've discussed of this subf family of of kos primes and so in particular by by performing this analysis for this subf family one can show that the error sum of kos primes uh tends to one as as k goes to infinity and one can actually get very precise error terms uh for for this family. Um however the the conjecture uh of 1196 is about an arbitrary set a and not this kind of special family with structure and so um this turns out to incur uh compounding cost. So if you wanted to study the first J prime factors, one would have to pay uh this kind of uh kind of J uh uh uh factors exponent uh kind of growing uh uh exponentially. Uh and this turns out to lead to a technical analysis of a certain iterated optim integral optimization problem um which is quite hairy and still actually remains an open question uh uh even today. Um uh however um uh by contrast it turned out uh GBD 5.4 uh found uh essentially a way to kind of cut this Gordonian knot of of difficulty and uh instead uh reframe the the the initial setup of the problem. Um so it introduced these uh weights uh b x of n which uh are defined in terms uh of the von mangle function in this following kind of peace-wise form where we have 1 / n uh log^ 2n n and then we have two sums over the von mangle function one involving uh prime powers less than y and another bigger than y for some parameter uh y that's uh carefully chosen. And uh this results uh by by suitably applying it in in a in a markup chain uh re results in a slick poof where everything uh in these two terms uh these two sums end up cancelling uh and reduces to this uh very nice key identity of the sum of uh lambda of q is equal to log n. So that just this uh essentially unique factoriization. Um but similarly uh the weights B of X themselves uh appear quite odd uh and very much less conceptual at first glance and it's only very much at at the end one can kind of reverse engineer that that B of X were essentially reverse engineered in order to to reduce to this key identity. So in the same way that even the vomal function itself was uh you know was defined in order to set up this this very nice relationship with the primes. Um and uh in particular uh so Sebastian Bubck at OpenAI created this very nice uh ones slide proof of the of the problem which I encourage you to look at uh on your own time uh which contains all the uh uh identities and uh basic definitions and in one uh slide concludes the proof uh not just of this upper bound but actually uh GBT's proof actually gives a quantitative uh secondary ary term that decays like big O of 1 / log x. So this was actually stronger than what was conjectured by uh sar and zi namely getting this quantitative upper bound. Okay. So uh in the kind of next uh portion of the the talk I'd like to describe uh some related uh results that uh depend on similar techniques. Um so in particular if we uh take an abstract viewpoint uh and we consider a primitive set um this is uh specifically an anti-chain um for the partial ordering uh of integers by divisibility. So in other words uh no number in a primitive set divides another which is the same thing as saying that no two uh elements are comparable for the uh order uh for for the relation of divisibility and so one can consider the dual notion of a chain um in this context. So uh if the operation is divisibility the chain has that every two elements are comparable and in the case uh of interest this simplifies to the uh notion of a divisibility chain. So in other words uh a sequence of integers uh d1 d2 and so on where each number strictly divides the next one in the sequence and divisibility chains have been studied for quite a long time. Um and there's a landmark uh theorem of Davenport and Nerdush from the 1930s which says the follow. If a set uh of integers has positive upper log density delta then a must contain an infinite divisibility chain. And just to recall uh upper log density means uh is defined as the limb soup. So delta is defined as the limb soup of 1 / log x times the sum of the harmonic series 1 / n for n in our set up to x. And so if uh our set has positive density then it must contain an infinite chain. And this davenport theorem is maybe an example of a broader cominatorial theme. Namely that if a set is large enough it must contain structure. So maybe uh people in the audience are familiar with perhaps like Zeades theorem which says that if a set has positive density then it must contain arbitrarily long arithmetic progressions. So in that sense if a set is large then it must contain additive structure in the form of a uh arithmetic progression. And similarly here in the Davenport theorem uh if a set is large enough it must contain multiplicative structure. So this is a a very broad theme and in particular uh Erdocy and Zamari in the same time period were in the in the 1960s were interested in a quantitative form of the Davenport error theorem uh for for divisibility chains and they made a remark uh saying that one can study the problem using either log density or double log density um but the latter actually turns out to be more interesting and actually more natural in this setting. So they conjecture um that if a set has a positive uh upper log density delta then there is an infinite divisibility chain d uh contained. So not only is it an infinite uh chain but it actually grows at least as fast as uh uh delta* log y when truncating uh the chain at at y. So and this occurs for an infinite uh subsequence of y's tending to infinity. So in other words infinitely often our divisibility chain d grows like log y times this constant delta. And uh just to recall so the double log density is defined or the upper double log density is defined as the limb soup of 1 / log x uh times the series of 1 / n log n for n in our set up to x. And so here perhaps it's uh uh very nice. So number one one over n log n is the essentially the uh second derivative. Um and it's very nice that this is also naturally occurring in in these airdri sums. So there's a very kind of direct connection between uh this problem and the uh other problems we've been looking at. And in uh formulating their conjecture they actually prove this lower bound of eus gamma * delta log y. So their conjecture is the statement that uh they could remove this factor of e to the gamma uh in the denominator. And uh uh [snorts] it turns out uh that the uh same machinery of using these von mangle chains uh also yields uh a proof of being able to remove this factor of e to the gamma and uh prove problem 1217 of of error sim. So, so this is a a very natural kind of dual problem that is also resolved uh just uh using the same uh techniques and um even further uh one can study what has uh been sometimes termed as a more master theorem. So uh the original edric primitive second conjecture was a statement that the maximum edger sum over all primitive sets is the set of primes. So one could then ask um if one throws away the primes and just looks at composite numbers uh you can ask what is the remaining uh maximizer uh among composite numbers. So the kind of uh conjecture uh any any any any takers uh in in the audience? Um >> I'm going to so I'm going to guess that it's products of two primes. Yeah, exactly. So, so once one throws away the the primes, uh the next maximizer is the tus primes and uh this was a conjecture of banks and Martin um and more generally they predicted a whole network of of conjectures uh in particular that um uh for any k integer k and any subset of primes q then the uh primitive sets um of which have at least k prime factors all of whose prime factors are in our specified subset q. Then the order sum of a is at most the order sum of the k almost primes uh q to the k. So these are exactly the set of numbers uh with k prime factors all in q. So this products this kfold product set. So this is a simultaneous generalization of uh many of the problems we've seen. Um and it's uh I think quite beautiful giving this hierarchy of uh of nested uh uh maximizers and in particular if one specializes our set A uh to be uh the K plus onefold product set Q to the K uh this is predicting that um in particular we have this infinite kind of chain of inequalities that f of uh the the primes f of q is bigger than f of the two most primes uh q ^2 and so on. So we have this infinite monotonic uh inequality um for all k. Um however uh so so some uh work on this special case of just looking at primes. Um already in the '90s uh Jeang had proven that the the primes uh p are maximizers among the kos primes. So the average sum of p to the k is the most the average sum of f to the p uh for any k. Uh however uh uh almost accidentally I found uh actually a counter example and uh proved that uh actually the numbers with exactly six prime factors uh turn out to be a minimizer uh among all km primes which I was uh quite shocked to find. Um and moreover in uh more recent work uh with uh Gordetski and Wong um and uh uh also uh uh with Putty uh uh just uh a couple months ago combining uh cases we have that uh it turns out um we have uh monotenicity uh for all K. So namely that the order sums of uh the prime these k almost primes uh turn out to be uh uh uniformly increasing which is the opposite of the banks and Martin conjecture. However, if one restricts one's attention to uh the primes without two so the odd primes then you actually recover uh this uh monotonic uh uh decay which was predicted. So it was only by removing the odd prime two, the oddest prime of the very first uh uh two uh that one recovers uh this uh chain of inequalities predicted by Banks and Martin. And back in 2023 uh Gordetsky and Wong and I proved this for for all sufficiently large K. And then actually uh uh with uh Potty uh he was able to uh uh actually shore up the and and confirm the the inequality for for every single K which was very was which was very nice recently. So um so based on this failure at uh just the prime p equals 2 um it's natural perhaps revise uh the bank's modern conjecture um just to restrict our primes to be odd and so that if uh q doesn't include the the prime two then any primitive set of numbers with at least k prime factors all in q should be maximized by whose air sum is maximized by the kos primes uh Q the kful products at Q to the K and uh moreover it uh turned out this method is uh flexible enough to also handle this uh very broad kind of master constructor of Banks and Martin uh in the odd case. So uh namely uh uh we take any odd primes uh Q and any K then the K-fold uh uh product set Q to the K is the maximizer for for error stumps um in this family and uh I just find this very quite beautiful that this one uh construction turns out to be flexible enough to be adapted uh to all these different problems and so taking a step back uh for for context maybe. Um the definition of a primitive set is very simple just the no number divides another in the set. um and hence it admits a very broad class of sets uh with potential very pathological examples if we if we recall the the construction of Bessakovich um from the beginning and uh nevertheless this odd version of the banks Martin conjecture uh asserts that the the class of primitive sets even though it's very broad with pathologies nevertheless has this very nice structure once we're using the the kind of metric of of these edger sums uh in a hierarchy of these maximal elements of of Q to the k at least k primes and I I find that quite uh quite nice. Um and uh maybe in the remaining time I'd like to kind of maybe step back and uh think about some broader motifs of of which uh this uh is a kind of case study. So air 1196 maybe uh involves maybe two broad themes that uh one seen in other examples. uh so in particular the discrepancy between the perceived difficulty uh before uh and after a proof. So um one can really cut what can be uh perceived a lot of technical analysis in a Gordian knot. Um uh so when this result came out Terry Towel mentioned uh the finite field kaya conjecture which uh was resolved by Dro in 2009 um as a grad student uh in just a few pages. Uh but prior to that um Terry had several papers in a sequence with with Borgan where they were uh iterating iteratively coming up with uh more elaborate and uh refined constructions to get uh more progress. Uh which was then eventually kind of uh all that uh complicated uh uh reasoning would suggest um that uh the final result might be quite uh long but really kind of simplified everything at the end. uh and similarly in the u more recent example of the sensitivity conjecture of Hong where one had a this uh kind of long-standing problem um whose eventual proof turned out to be quite compact and far shorter than the prior work had suggested and uh maybe a kind of psychological uh facet to this to this uh problem was that uh after the initial proof uh waited maybe 60 years uh to to be solved then these alternate proofs and these other problems other related problems really kind of followed and and were solved within days. Um, and so the method uh was very uh flexible to to solve these other problems. Um, and almost needed, you know, this this one push uh to nudge. And I'm almost reminded of uh the story of you know Roger Banister when uh uh you know in in the 20th century when he broke first broke the the 4-minute mile which was thought to be impossible but after it was done and soon after uh a slew of other runners uh had the psychological uh boost and then they too uh went to break the the the record. Um and also I've um maybe been uh uh reflecting on on these developments more broadly and especially in in recent months with with other uh uh results uh solved uh with AI assistance or autonomously and um uh an analogy for this problem I like to think about is uh uh with chess. Um so uh in the case uh of chess, humans had long uh studied and internalized uh the strategies and openings over over decades and centuries and uh it was quite stable. One had a sense of what the strongest opening lines were uh the first few moves. Um but in uh the '9s and 2000s once chess engines became quite strong uh they found uh subsequently that uh certain um openings that uh humans had overlooked actually turned out to confer certain technical advantages uh which had been overlooked because they maybe subvert some human aesthetics or conventions that people had established. And uh that was very much the case in uh uh this problem with introducing the von mangled uh function with with these kind of counterintuitive weights that um I guess one could suggest uh maybe even to back air back in the 1930s to to make this choice and then the problem would kind of dissolve itself quite quickly. But uh the real kind of uh initial hurdle is to come up with the idea in the first place that one could even look in this in this direction. Um and maybe a last uh uh reflection was that uh with this uh uh this problem. So when it was solved in April, this was maybe uh one of the first examples of uh an AI proof um that uh not only his proof but turned out to be uh not just a a raw literature search uh which had maybe been uh seen uh last year but actually presenting genuinely uh uh new math or at least uh uh novel combinations of existing techniques. And uh we've seen perhaps uh even more recently uh other other such examples um motivating the question I I've gotten uh by a number of people uh whether we've kind of reached uh uh so-called move 37 for math uh referencing the uh uh alph uh moment where uh AI u go engines were able to beat the the best uh go masters in the world in this ancient game um in a particularly creative move that uh one hadn't thought of. And uh my response at least right now is that no, I I don't think we've seen um uh uh an AI proof that has produced a um I would say genuinely novel construction or generally novel definition or theory. Um and so far it's been uh clever combinations of existing techniques and um yeah so I I think that is a a threshold we have yet to cross um which uh I'm uh you know quite fascinated by um and it's also maybe worth uh uh mentioning that in uh the problem alpha go itself so this was back in 2016 um this was uh I think uh move 37 was a uh maybe a particular moment in time that uh the public had kind of latched on to. This was uh just one move in a sequence of uh several games. Uh I think a game uh a sequence of five games uh up to five where uh each move uh so so the uh in the chess uh sorry in the in the go world um uh the Lisa Dole the the chess the the go master had uh obtained one victory. Um and uh maybe identifying that one move uh was was kind of nice, but um to to shape a story around, but I think the broader story was that uh there was these larger strategies that were sometimes uh uh very dynamical and not evaluating uh uh positions in the way that humans would have uh allocated uh uh territory in the game and and maybe kind of provoked a new line of thinking that I think um maybe subsequently go um players have have adapted to. And I think there was actually um a recent uh announcement that there was some uh human uh uh success uh playing uh even just a couple weeks ago of a go uh master uh winning against an AI um uh uh kind of the best AI system uh with an affordance of two two stones as an advantage. Um so it's it's still very uh an interesting story. Um, but I'll I'll leave it that uh for now. Uh, thank you.