google-deepmind / google-deepmind/formal-conjectures

Possible misformalizations II

Open
#4,923 0 comments 2 reactions 0 assignees View on GitHub
misformalization
Dominant language
Lean
Stars
1.3k
Forks
485
Avg merge
1d 20h
Merged PRs (30d)
327

Description

## Purpose

This is a follow-up to #4896. I found several more statements that appear to
be provable without answering the intended mathematical question.

These may be misformalizations, so I am collecting them here for review.

Each checkbox below is one independently trackable item. A dedicated issue or
PR can be linked on the same line and the item checked once resolved.

## Exact self-answers

- [ ] [Erdős 33](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/33.lean)
— **Problem:** the entire unknown infimum/limsup expression can be copied into
`answer`, so the theorem closes by `rfl`. **Likely fix:** require a concrete
value or formula independent of the target expression.

- [ ] [Erdős 329](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/329.lean)
— **Problem:** the unknown supremum can be copied into `answer`, so the theorem
closes by `rfl`. **Likely fix:** require a concrete value independent of that
supremum.

- [ ] [Erdős 348](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/348.lean)
— **Problem:** the target set of pairs can be copied into `answer`, so the
theorem closes by `rfl`. **Likely fix:** state the proposed set explicitly,
independently of the target set-builder expression.

- [ ] [Erdős 409, part iii](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/409.lean)
— **Problem:** the unknown density `α` is already a theorem parameter and can
be returned as `answer(α)` by `rfl`. **Likely fix:** if the source predicts a
concrete density, state it directly; otherwise remove the misleading open
`answer` slot.

## Reflexive asymptotic answers

- [ ] [Erdős 422 `growth_rate`](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/422.lean)
— **Problem:** the target function itself can be used as the Big-O answer;
`isBigO_refl` then closes the theorem. **Likely fix:** require an independently
specified comparison scale or restrict the permitted answer family.

- [ ] [Erdős 539](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/539.lean)
— **Problem:** `cofactorThreshold` itself can be used as its Big-Theta answer;
`isTheta_refl` closes the theorem. **Likely fix:** require an independently
specified asymptotic formula or comparison family.

- [ ] [Erdős 789](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/789.lean)
— **Problem:** `subsetSumThreshold` itself can be used as its Big-Theta answer;
`isTheta_refl` closes the theorem. **Likely fix:** require an independently
specified asymptotic formula or comparison family.

## Degenerate witness

- [ ] [OEIS A211417 `general_divisibility`](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/OEIS/211417.lean)
— **Problem:** `D = 0` makes the current existential vacuous. **Update:** the intended version appears true with the explicit positive witness `D(r) = lcm(1,...,r)^|{1 ≤ i ≤ r : gcd(i,30)=1}|`. **Likely fix:** state this witness, or require `D > 0`. The general proof is paper-complete but not yet Lean-checked; the four fixed statements are separate in #5010.

## Incorrect boundary and indexing

- [ ] [OEIS A111291](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/OEIS/111291.lean)
— **Problem:** every `1 < x < 2` is a counterexample: `countRefactorable x = 1`, but `x/(2*log x) > 1`.
**Likely fix:** use an eventual or explicitly sufficiently-large bound.

- [ ] [OEIS A109074](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/OEIS/109074.lean)
— **Problem:** `n = 1` gives `frac 1 = 1` but `b 2 / b 1 = 3`. Also, the helper `b` is the ternary Fuss–Catalan sequence, not A005156.
**Likely fix:** define the actual A005156 and use the data-compatible shift `A005156(n)/A005156(n-1)`.

## Related tracking

- #4892 — Erdős 319
- #4919 — Erdős 688
- #4922 — Erdős 142

## Caveat

This list was organized with AI assistance from my long working notes and may
contain transcription or interpretation errors.

Contributor guide

Open the contributing guide

Research direction

Start with the linked Lean files under FormalConjectures/ErdosProblems and FormalConjectures/OEIS, checking each statement and its proof for the listed self-answer, reflexive, vacuous, boundary, or indexing issue. Compare the formal statement with the intended mathematical claim and verify that each correction compiles without closing trivially; completion is tracked by checking the relevant item or linking a dedicated issue or PR.

Written by the indexing model from the issue text.

Assessment

Domain
tooling
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.