Classic problem about the limits of addition

In his 1965 paper, Erdős showed —in a proof that was just a few lines long, and hailed as brilliant by other mathematicians —that any set of N integers has a sum-free subset of at least N/3 elements.

Still, he wasn’t satisfied. His proof dealt with averages: He found a collection of sum-free subsets and calculated that their average size was N/3. But in such a collection, the biggest subsets are typically thought to be much larger than the average.

Erdős wanted to measure the size of those extra-large sum-free subsets.

Mathematicians soon hypothesized that as your set gets bigger, the biggest sum-free subsets will get much larger than N/3. In fact, the deviation will grow infinitely large. This prediction  that the size of the biggest sum-free subset is N/3 plus some deviation that grows to infinity with N —is now known as the sum-free sets conjecture.

Comments

Post a Comment

Empathy recommended

Popular posts from this blog

Hamza Chaudhry

"Although a nuclear confrontation based on fake intelligence may seem unlikely, the stakes during crises are high and timelines are short, creating situations where fake data could well tilt the balance toward nuclear war. "The evolution of nuclear systems has led to further ambiguity in crises and shorter timeframes for verifying intelligence. An intercontinental ballistic missile from Russia could reach the U.S. within 25 minutes. A submarine-launched ballistic missile could arrive even sooner.  "Many modern missiles carry ambiguous payloads, making it unclear whether they are nuclear-tipped. AI tools for verifying the authenticity of content are not sufficiently reliable, making this ambiguity difficult to resolve in a short window. "The likeliest nuclear hotspots are also the arenas involving actors with low levels of trust on both sides — be that the U.S. and the Chinese Communist Party or Russia, or India and Pakistan. Even if communication is established in a...
Read more

Swarm 🦹‍♂️

"Knowledge discovery from data typically includes solving some type of an optimization problem that can be efficiently addressed using algorithms belonging to the class of evolutionary and bio-inspired computation .  "In this chapter, we give an overview of the various kinds of evolutionary algorithms, such as genetic algorithms, evolutionary strategy, evolutionary and genetic programming, differential evolution, and coevolutionary algorithms, as well as several other bio-inspired approaches, like swarm intelligence and artificial immune systems.  "After elaborating on the methodology, we provide numerous examples of applications in astronomy and geoscience and show how these algorithms can be applied within a distributed environment, by making use of parallel computing, which is essential when dealing with Big Data."
Read more

Digital ID tracking system

The U.S. Transportation Security Administration (TSA) has moved forward with regulations establishing a smartphone-based national digital ID and tracking system, disregarding objections from organizations like the Identity Project. These new rules are based on the REAL-ID Act of 2005 and set the standards for how states will issue digital versions of driver’s licenses or ID cards, which will be accepted by the TSA and other federal agencies for certain official purposes. However, these rules do not extend to airline travel, where no ID is legally required, despite the TSA’s misleading statements to the contrary. Under the TSA’s new regulations, digital IDs can only be issued to individuals who already possess a physical driver’s license or state-issued ID card. Additionally, individuals are still obligated by state laws to carry their physical ID while driving, even if they have a digital ID on their smartphone.  This shift is not primarily about improving driver’s license technolo...
Read more