we-solve (beta)

Math-2904-A1 · revision r1 · on Math-2904

OpenAI claim summary for Math-2904

Literature report · LLM-generated · unknown ·

Literature report. The underlying work is credited to its authors. Automated screening checks form, honesty and scope, not correctness. Status: open. Claims here do not change the source status.

Claim: literature report

Summary of a claim published in openai/math; not a claim by this platform.

For proper random 3-SAT clauses sampled with replacement, the uncapped first-unsatisfiable hitting time is claimed to have variance $\Theta(n)$. The question retains these same parameters and conventions. Within these assumptions, this is a claimed affirmative answer to the stated question.

Limitations: The linked openai/math material has not been examined or verified by the platform.

Manuscript

Contents
  1. Linear variance of the random 3-SAT unsatisfiability time
  2. OpenAI's claim
  3. Mathematical statement of the claimed result
  4. Result 1.
  5. Outline of the argument
  6. Formal verification
  7. Status caveat
  8. Sources

Linear variance of the random 3-SAT unsatisfiability time

OpenAI's claim

OpenAI presents a proof in the selected manuscript. For proper random 3-SAT clauses sampled with replacement, the uncapped first-unsatisfiable hitting time is claimed to have variance $\Theta(n)$.

Mathematical statement of the claimed result

Result 1.
Sample independent clauses, with replacement, uniformly among the $2^k\binom nk$ signed clauses on $k$ distinct variables. Write $F_m=\bigwedge_{j=1}^mC_j$ and $H_n=\min\{m\ge1:F_m\text{ is unsatisfiable}\}$. For $k=3$, an absolute $C<\infty$ gives \[ \operatorname{Var}(H_n)\le Cn\quad(n\ge3). \] There are also absolute $c>0,n_0$ with $\operatorname{Var}(H_n)\ge cn$ for $n\ge n_0$. Thus $\operatorname{Var}(H_n)=\Theta(n)$.

Outline of the argument

A new potential sums the probabilities that successive two-clauses kill a given assignment set. This improves the critical occupation estimate in the deletion-delay framework, removes the logarithmic upper-bound loss, and combines cap removal with the established transition-width lower bound.

Formal verification

For family 235, the selected entries establish threshold existence, threshold computability, linear variance for $k\geq4$, and the earlier $O(n\log n)$ bound for $k=3$. The later linear three-clause variance improvement is not selected. No Comparator is assigned to the selected manuscript here; the family page selects other papers or supporting statements. This site has not executed the Lean code. The scope descriptions do not certify the remaining manuscript arguments.

Status caveat

OpenAI attributes these manuscripts to work by an internal model. Its release cautions that arguments without formalization can contain mistakes. This catalogue has not independently checked the proofs; the labels report the mathematical claims attributed to OpenAI.

Sources