Surprise computer science proof in combinatorics

Hey nothing wrong with that! Huge fan of Terry Tao. Something magical about how their brains work.

Plus much shorter write-up from Bloom and Sisask: https://arxiv.org/abs/2302.07211

The first half page finally made me understand the problem. I didn’t get it from the article.

According to the OEIS [0], the set has size 27; you can find its terms in the Dybizbański reference [1]. Presumably, it's been computed up to N = 211, where the B-file ends.

[0] https://oeis.org/A003002

[1] https://doi.org/10.37236/2061

>In late 2021, Kelley and Meka were analyzing the chances that a team of players in a certain cooperative game would be able to win, a standard type of computer science problem. It occurred to them that techniques from research on the size of progression-free sets might be helpful. But they found it easier to directly study those techniques than to apply them to the cooperative game. “My best idea for how to make progress on this problem [was] to actually improve the tool itself, not to use it in a more clever way,” Kelley said.

I wish they went into more detail about how this problem was relevant to the other problem.

> What's the point of spending "time" (brain cycles) on such problems?

What's the point of anything?

> Is it just a mathematician's version of brain teaser?

All of mathematics can be characterised as "brain teasers". Make of that what you will.

> What useful development comes out of such?

I'm not qualified for this particular example. However, it seems quite number-theoretic, and number-theory has given us such "practical" things as asymmetric encryption and universal computation (Turing's famous paper from 1936 was titled "On Computable Numbers", after all).

It's normally extremely hard to guess the applications of this kind of research. Having said that, almost all modern cryptography relies on maths that was not obviously applicable at the time.

This has significant implications for randomness and entropy.

I can already see it being useful for verifying entropy and for verifying anonymization of statistical data.

Neural networks were first prototyped in the 1950's [1]. How practical was it to study them back then?

Aleksandr Lyapunov's theory of stability for dynamical systems, which forms the bedrock for much of control theory, was first proposed in 1892 and went unnoticed until the 1930's [2]. How practical was it for Lyapunov to study that topic?

It's virtually impossible to predict which mathematical tools will be "practical" or "useful" in the future. The point is that if someone needs the tool down the road, they'll have access to the solution due to the efforts of these mathematicians.

[1]: https://en.wikipedia.org/wiki/Neural_network#History

[2]: https://en.wikipedia.org/wiki/Lyapunov_stability#History

All fundamental research is odd like that. Someone has to make significant progress on a 'useless' topic before some semblance of usefulness starts becoming visible.

Sometimes, discovering these proofs makes the math easier. If we know X is the case for all Ys, and X is easier to compute, you can use X where you would use Y before. Of if you know X is true for all Ys, you can skip the part where you have to verify that your Y has X property. Because we now know it must have it.

And it's math all the way down in computers. So anything that makes math easier or quicker has the potential to affect anything a computer can process.

A Hash Table's double hashing [1] creates an arithmetic progression. Improving bounds of this theorem could lead to faster, smaller hash-tables. This is the first wild speculation I could come up with.

[1] https://en.wikipedia.org/wiki/Double_hashing

Mathematics continually surprises us when seemingly disparate areas suddenly become linked, sharing some sort of relationship that was not appreciated until much later.

Some think mathematics is something like a physical law, or property of the universe. So figuring out such things may be like fundamental physics research. Hard to quantify the value, but there is value. Seemingly unrelated developments in mathematics have had a habit of helping to solve problems in physics in the past, at least. I don't think anyone really expected the exciting new mathematics of statistics in the 18th century, to one day be relevant to physics. But it would be.

Most of the other comments focus on how and why theory research often leads to "practically useful" outcomes down the line, so I'll instead say that not all research has to be practical. Sometimes people do things just because they're interesting and fun.

Why do people play board games, or video games, or sports? Why do people read fiction? Why do people have hobbies which strictly distract from productive work time? The answer to any of these questions is the same as the answer for "Why do people do theoretical research?": it's fun.

Understanding the fundamental nature of numbers and sets will allow a person to avoid working on solutions to their "real world" problems which would be precluded by that nature.

Take cryptography for instance. Why large prime numbers? Why elliptic curves? If you have proven the fundamental mathematics behind factoring large primes, then you have a basis for thinking that a cryptographic system based on large primes will be reasonably secure.

Many of the developments you use everyday are based on the understanding of just such "brain teasers" :-).

lets just hope that politicions who controls the flow of resource are not as shortsighted as you or we are doomed. The computer and all the software won't be exist without this boring and pointless mathemathics from a long time before

There is no direct practical reason. Other people are giving you the long term outlook view, why it is valuable in aggregate, but if you were aiming for immediately practical results neither math nor CS would fit the bill.

I can't speak for others but for me math is kind of like a brain teaser on crack. It is immensely satisfying to think about and I would imagine most mathematicians get a similar kick out of it. Not a mathematician myself mind you.

Understanding mathematics before we understand what problems it solves happens all the time. Maybe nothing will come of this, but because we can't know that, it's worth researching.

People didn't believe there was non-Euclidean geometry and not long after the taboo was broken, we had General Relativity. Einstein was a genius, but he did not invent the math for GR. Mathematicians like Riemann, Minkowski, Hilbert, Ricci, Levi-Civita and others created the mathematics for it first.

Finding the area under a curve or the tangent line of an arbitrary curve were considered two unconnected brain teasers until Calculus was invented by Newton and Leibniz and applied to gravity by Newton.

The "Math First" approach has done more than enough to prove its continued viability and without it you wouldn't have been able to type that here.

Maybe the question is what useful developments haven’t come from mathematical play originally, and can’t trace their lineage to abstract brain teasers?

>What useful development comes out of such?

Mathematicians aren't concerned with that at all. If something they do ends up being useful to science and engineering, then wonderful. But it's not the point.

The flippant answer is https://abstrusegoose.com/504

The fallacy is thinking that this was the puzzle. This is just one piece in a puzzle that's so big no one person can see the whole thing, and that we're using as a blueprint for large parts of modern civilization while still figuring it out. We don't even know whether we've completed most of the puzzle, or whether the puzzle is actually vastly larger than what we've already put together.

If you can't see why this is useful, then great: that's literally what it means to be a layman. But that also means that you don't know enough about the subject field for the real answer (the one that explains what other maths this affects) to satisfy your question because you won't know why _those_ things would matter.

So you're going to get the layman's answer: "because this shows that any work already performed in the assumption of its truth is now known to be valid", which is critically important because a lot of what maths is used for in real life is based on assumptions about the properties of numbers. Now others can stop wasting their time trying to determine whether this aspect of number theory can be relied upon, and under which circumstances, and trying to find all expressions of it in both software and hardware in order to determine whether those might have problems on a case-by-case basis. And at the same time, this result allows others still to move forward with work that is known to rely (in part!) on this property either being true or false, for which it was previously uncertain whether it would even be worth the effort because it was unknown whether the results would turn out to be useless because no one knew whether the basis it relied on was flawed.

As for what useful development comes out of things like this:

points at the computer you're using to comment on HN threads, and every single application on it that you've ever used

That.

The gist of the insight of exercise is that one is conditioned, even if the exercise itself seemed pointless, for the unpredictable in later situations.

Very similar answer to this - https://www.themarysue.com/tyson-space-exploration/

A practical person doesn’t usually discover or invent something which turns out to be practical in the long run.

I've spent a lot of time and brain cycles over the last decade writing software, entire products actually, that now sit as motionless bits on a disk somewhere, unused and useless.

In the process of creating them I had a lot of fun, honed my existing skills and picked up new ones, broke out of various boxes I had been stuffed into in terms of how to architect systems, and just generally worked out my creative muscles.

I've also written a lot of software that is useful and used, and in a practical sense makes (lots of) money.

It's meaningless to break out the time and cycles spent on one Vs the other. The necessary skills required were enabled by one another. Moreover it would have been to a large extent impossible to determine a priori which would be which.

Am I an impractical person because I've spent time and cycles on the former?

The point is to advance knowledge of mathematics. Knowledge is a practical pursuit in and of itself.

One can see it as peeking behind the veil to view the underlying structure of the universe we live in. It permits certain things and does not permit others.

I have a friend working on lidar for a military contractor. He uses these exact theorems to design beam pulses for measuring distances of asteroids and stuff. The idea is to construct beams so that you can tell by the autocorrelation function the exact distance away an object is. It turns out that these weird kinds of integer sequences can help you design beams that give the autocorrelation function this property.

Lazy loading solutions doesn't work when there's no library of solutions to pull from.

Humanity already tried thinking it was better than the selfless pursuit of knowledge, that path leads nowhere good.

Some number theory results about sequences and progressions can be applied to create more efficient algorithms to approximate the solutions to multi-dimensional integrals that come up in physics (especially solid state physics on lattices).

Solid state physics problems of that sort are used in the process of engineering new materials (e.g. a more efficient dielectric for capacitors, a magnetic material that can store magnetic memory data at higher temperatures without destablizing, a higher temperature superconductor, etc). Idk if this particular result has such an application, but I wouldn't be surprised if it did.

In addition to solid state physics, "special functions" show up in many areas of applied math and physics, including the design, calibration, and data analysis of/from MRI machines and antennas. Many special functions including the hypergeometric functions can be approximated more efficiently using fancy number theory algorithms.

There is also a broad category of physics and chemistry problems that are best solved by Monte Carlo simulations, and sometimes Monte Carlo approximations can be made using many fewer iterations by choosing a set of points within the sample space that satisfy number theoretic constraints.

Also, physics models often inspire machine learning models so it's not impossible that some niche ML algorithm could eventually benefit from a faster algorithm that uses this result or a derivative of it.

None of these directly answer your question about a definitive application for this particular number theory result, but I hope it gives you an idea of what it could potentially be used for. The closest analogy I know if is that certain multi-dimensional Monte Carlo integral approximations can be done orders of magnitude more quickly if you choose lattice points whose coordinates satisfy some similar-ish constraints to the ones described for this problem.

Before cryptography, all of number theory was considered just one brain teaser after another. Without those brain teasers we wouldn't have secure private communications.

Well, you can now use this as a tool to show that if you can reduce part of a problem to creating a progression free set you can use that to show the complexity of a problem.

The ways I've seen combinatorics (and graph theory!) interact with software engineering is typically showing that a problem is too expensive to solve at scale.

For a long time certain mathematicians took great pride in studying the most useless part of their field, prime numbers. Without their studies we would not have modern cryptographic techniques (RSA, SSL, HTTPS). And no bitcoin either.

Eh, someone just suggested that a bound of this form might break some cryptographic assumptions for finite fields of (large) prime order. (This is not obvious to me, but it's a point that I think is worth considering, and already would show that such a result is useful.)

It's very hard to know how these things end up being useful. Even if a specific piece of knowledge isn't useful by itself, it can lead to things that are useful down the line. It's both very hard to know which ones will be, or which ones do lead to actually useful results; for example, think of work on propositional logic which ends up being the bedrock of computation, work on elliptic curves (cryptography), work on PDEs (physics), quantum physics (transistors), photonics (communications), etc.

Some fields have pretty "fast-to-application" times, but it's not always clear which ones will _not_ yield useful results. Plus, and here's the real, honest answer: all of this shit is very fun! Why not do it?

I'm also a (somewhat) practical person, and that guides many of the problems I try to solve, but sometimes there's just such a tantalizing puzzle that it's hard not to resist! It's pretty damn hard to "only" work on "useful" stuff and not be just an ok academic/programmer/etc., you have to let yourself get nerd-sniped into doing random things. With very high probability, these little "side-quests" end up being very useful down the line, for one reason or another.

We're mortals, the only relevantquestion is "is it a better use of brain cycles than X".

Considering that way vaster amounts of brain cycles are devoted to making people watch one more TikTok video, then, I think this kind of brain-scratching is more useful than much of what most of us do.

My master thesis was about a problem that I could only find an NP solution for, but some of the underlying mathematical problems have not been studied/solved in depth yet, so I'm patiently waiting for a solution.

Ever heard about culture? I bet by useful you mean profitable

Did you read the article? The headline is pretty accurate, if not pretty abstract.

Any headline containing the word "bombshell", "destroys", "shocking" or things of that ilk are ALWAYS poorly written fluff, because editors are generally competent.

If there was an actual bombshell that would be the headline!

It wouldn't be "Surprise Computer Science Proof Stuns Mathematicians" it would be "Scientist solves Fermat's Last Theorem" or something

"Theorem shows how 3-term arithmetic progressions inevitably arise in large sets"

"Improved upper bound on density of integer sets containing no subset a,a+b,a+2b"

Ok, we've unstunned the mathematicians and added combinatorics to the title above.

You must be confused, the title specifies computer science and mathematicians - the default assumption here should be that if it is useful no one is going to realize for some decades.

> Ok, but what's the use of this data set?

Same use as the rest of mathematics: Entertainment for those interested in the topic.

"Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something."

https://news.ycombinator.com/newsguidelines.html

>there’s no point planting seeds because plants will grow anyway

did you have a bad maths teacher at some point?

The authors of the paper are academics in university CS departments with heavy math backgrounds (one with a B.S. in mathematics, another was a visiting professor at MIT dept of mathematics). I don't understand what you mean or how it relates to the article or surrounding circumstances.