017 Some simple open problems in Mathematics by Joseph Oesterle

Scientific concepts / nature phenomena / mathematical discoveries mentioned

1) Set theory (Frankl’s Union-Closed Sets conjecture)

Setup

• Consider a finite family ( \mathcal{F} ) of finite sets.
• The family is nontrivial (at least one set is nonempty).
• Union-closed: if (A,B \in \mathcal{F}), then (A \cup B \in \mathcal{F}).

Open problem / conjecture (Peter Frankl, 1979)

• Does there exist an element that belongs to at least half of the sets in ( \mathcal{F} )?

Known easy case

• If some member of the family is a singleton ({x}), the claim is immediate.

Partial results (state of the art mentioned)

• True when (|\mathcal{F}| \le 46) (Roberts and Simpson; work cited as 2010).
• True when the largest set size in (\mathcal{F}) is (\le 11).

---

2) Number theory / Diophantine representation (Strauss–Erdős–type “Egyptian fraction” conjecture)

Conjecture (attributed in the talk to Strauss & Aush; stated 1948)

For every integer (n \ge 2), do there exist integers (A,B,C \ge 1) such that [ \frac{4}{n}=\frac{1}{A}+\frac{1}{B}+\frac{1}{C}\,? ]

Reasoning / examples discussed

• For a particular (n), explicit decompositions sometimes exist.
• The speaker notes the problem is easy for many congruence classes.
• A “difficult” congruence class identified: when (n \equiv 1 \pmod{24}) (example given: (n=73)).
• An explicit formula for numbers of the form (3m+2): [ \frac{4}{3m+2}=\frac{1}{m+1}+\frac{1}{3m+2}+\frac{1}{(m+1)(3m+2)}. ]

Computational verification

• Verified by computer for (n \le 2 \times 10^{14}) (cited as completed in 2012).

“Statistical” / average-case result

• Terren (together with a collaborator—name garbled in subtitles) showed that for randomly chosen (n) in a large range, the average number of solutions ((A,B,C)) is on the order of ((\log n)^3).
• This does not automatically prove the statement for every specific (n).

Status

• Still open for the general “for all (n)” claim.

---

3) Dynamical systems / geometry (Triangular billiards periodic orbits conjecture)

Phenomenon

• A billiard trajectory in a triangle: a point particle reflects off sides using the usual law of reflection.

Periodic/closed orbit notion

• A closed trajectory (periodic billiard orbit): after some time, the path repeats.

Known “easy” case

• If all three triangle angles are < (40^\circ), a periodic orbit of period 3 can be constructed using geometry involving altitudes and cyclic angle/arc arguments.

Best known general results mentioned

• Computer-assisted technical work (Richard Evan Schan(s); cited as 2006) proves existence in cases where the largest angle is (\le 200^\circ).
• No general results above (100^\circ) except for “very special angles” (e.g., rational multiples of a flat angle).
• The talk asserts (as stated by the speaker): above (90^\circ), there is “never anymore” a periodic orbit of period 3.

Motivation / relation to smoother billiards

• For smooth convex billiards (boundary of class (C^1)), one can prove:
  • for each (n), there exists a periodic orbit of period (n).
• Triangles are harder due to nonsmooth corners (endpoint issues during reflection).

---

4) Combinatorics on sequences (Kővsky self-reproducing sequence conjecture)

Self-reproducing sequence

• Built from digits (1) and (2) using a “counting” rule:
  • the next block is determined by the counts of (1)’s and (2)’s in the previous block.
• Introduced by Kov(k)sky (subtitles: Kovski), with uniqueness implied by the self-reproducing rule.

Open problem / conjecture

• If (P_n) is the proportion of 1’s among the first (n) digits, does [ P_n \to \tfrac{1}{2}\quad \text{as } n\to\infty\,? ]

• Equivalently, the proportion of 2’s also tends to (1/2).

State of the art mentioned

• Proven bounds (Vasc, 1994): for large enough (n), [ 0.499 < P_n < 0.51. ]

• These bounds do not prove the limit equals (1/2).

---

5) Algorithms / optimization in puzzles (4-peg Reve’s? / optimal 4-peg Towers of Hanoi)

Classical three-peg Towers of Hanoi

• Minimum moves (a_n) satisfy: [ a_n = 2a_{n-1}+1, ] so (a_n) grows on the order of (2^n).

Open problem

• For four pegs, determine:
  • the minimum number of moves, and/or
  • whether a proposed strategy (published in 1941, credited to “Frame and Stewart” in subtitles) is truly optimal.

Known information

• The strategy is verified to be optimal for (n<30) by computer search.
• Beyond that, computation became too hard.

---

6) Computational number theory (square-freeness testing vs factorization)

Context

• Let (n) have (D) digits in base 10 (or large (D)).
• Factorization can be done in subexponential time (bounds described).
• Primality testing is doable in polynomial time (attributed to Agrawal–Kayal–Saxena, 2002).

Open problem

• Can square-freeness be tested in polynomial time?

Square-free means: in the prime factorization of (n), all prime exponents are 1 (no (p^2) divides (n)).

Comparison to known complexity

• No algorithm is known that is significantly faster than factoring; faster-than-factoring would already be a major breakthrough.

Analogy with polynomials

• Over polynomials, square-freeness can be tested by:
  • computing ( \gcd(p, p’) ) (with derivative),
  • and checking whether (\gcd(p,p’)=1).
• The speaker emphasizes there is no known integer analogue “like derivative.”

Bottom line

• Seeking a polynomial-time test for square-freeness, and a method that plays the same role as derivatives do for polynomials.

---

7) Combinatorial geometry (Erdős–Szekeres / “convex polygon from points” conjecture)

Conjecture (Erdős–Szekeres; stated around 1935 in the talk)

• Given (2^{n}) (or more precisely “(2^n) … plus/minus 1” as stated) points in the plane in general position (no three collinear),
• there always exist (n) points that form the vertices of a convex (n)-gon.

Sharpness

• The bound is sharp: with constructions, slightly decreasing the number of points fails.
• Example sharpness illustration (convex pentagon):
  • With 8 points (one less than the bound), one can arrange points so that no 5 of them form a convex pentagon (as described with points placed near a diagram).

Known cases and timeline (as mentioned)

• (n=4): due to Erdős and Szekeres (as said).
• (n=5): mentioned as due to “M. I think Mai” (subtitles garbled).
• (n=6): proved in 2006 by Szekeres and “Pet” (subtitles likely referencing known published work).

Biographical/collaboration notes

• The story is tied to Szekeres, and the talk mentions:
  • Esther Klein gave an earlier, less precise version in 1933, and Erdős and Szekeres quickly worked on it afterward.
• Additional note:
  • Szekeres later published works including one on spacetime/spinor geometry (outside combinatorics).

---

Researchers / sources featured (names as stated or implied by the subtitles)

• Joseph Oesterle (speaker; title references “Some simple open problems in Mathematics”)
• Peter Frankl (Union-closed sets conjecture; 1979)
• Roberts (partial result with Simpson; full first name not given in subtitles)
• Simpson (partial result with Roberts; 2010 cited)
• Strauss (Egyptian fraction conjecture; 1948 attributed)
• Aush (co-attributed with Strauss; name garbled—possibly an auto-caption error)
• Balo (name garbled; referenced in connection with a difficult example; identity unclear)
• Terren (average-case solutions result; collaborator name garbled as “elol”)
• Richard Evan Schan(s) (computer-assisted triangular billiards work; 2006; name garbled)
• Kov(s)ky (Kovski sequence / self-reproducing sequence; introduced 1965)
• Okuk (proved periodicity result for Kovksy sequence in 1966; name garbled)
• Vasc (1994 bounds on proportion of 1’s)
• Frame (four-peg Hanoi strategy source, 1941)
• Stewart (four-peg Hanoi strategy source, 1941)
• Agrawal (AKS primality testing; 2002)
• Kayal (AKS primality testing; 2002)
• Saxena (AKS primality testing; 2002)
• Erdős (Erdős–Szekeres convex polygon conjecture)
• Szekeres (Erdős–Szekeres convex polygon conjecture; also proof for (n=6) referenced)
• Esther Klein (earlier talk version in 1933)
• “Peters” (referenced in context of (n=6) and publication timing; exact person unclear due to subtitle noise)
• Lin Peters (mentioned as coauthor on a late paper; name likely garbled)

Where a name is likely garbled by auto-captions, it’s reproduced as closely as possible to the subtitles; exact spellings/identities may differ.