---
id: "2026-11-05-3-uniform-hyperclique-hypothesis-false-chatgpt-sol"
url: "https://postcutoff.com/e/2026-11-05-3-uniform-hyperclique-hypothesis-false-chatgpt-sol/"
as_of: "2026-11-09T21:13:00+01:00"
date: "2026-11-05"
date_precision: day
category: science
importance: 4
confidence: high
status: [Event confirmed, Awaiting review]
verification: Preprint only
sources: 1
editor: human editor
human_review: null
version: "2026-11-05"
---

As of: 2026-11-09 21:13 CET.
Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/
Canonical page: https://postcutoff.com/e/2026-11-05-3-uniform-hyperclique-hypothesis-false-chatgpt-sol/

# 3-uniform hyperclique hypothesis refuted with ChatGPT Sol 6.1

Full title: Chan, Itakura, Ma and Yu refute the 3-Uniform Hyperclique Hypothesis; both proofs obtained with ChatGPT Sol 6.1

An arXiv preprint by Timothy M. Chan and three co-authors gives an O(n^3.957)-time algorithm for finding 4-hypercliques in 3-uniform hypergraphs, refuting the Lincoln–Vassilevska Williams–Williams (2018) hypothesis that underlies many conditional lower bounds, and giving a faster exponential-time algorithm for Max-3-SAT. The authors say both of their proofs were obtained using ChatGPT Sol 6.1 and then rewritten by them. Unrefereed preprint.

## Key facts
- arXiv 2611.06813, announced 5 Nov 2026; authors Timothy M. Chan, Reina Itakura, Zhiyuan Ma, Yuancheng Yu
- Main theorem: 3-uniform 4-hyperclique in O(n^3.957) deterministic time (Theorem 2.8), via reduction to rectangular matrix multiplication; implies O(n^(k−ε⌊k/4⌋)) for k-hyperclique, k ≥ 4
- Implies an O(2^((1−ε/4+o(1))n)) algorithm for Max-3-SAT, improving Alman–Chan–Williams (2016), and disproves what some called the Max-3-SAT Hypothesis
- Hypothesis 1.1 was introduced by Lincoln, Vassilevska Williams and Williams (SODA 2018) and used for lower bounds on induced 4-cycle detection, Klee's measure problem, hypercycles and database problems
- AI disclosure: 'Both proofs in this paper are obtained using ChatGPT Sol 6.1, prompted by different suggestions. This manuscript is human-written: we (the authors) rewrote the proofs … (the initial solutions were not easy to understand)'

## What happened

On 5 Nov 2026 Timothy M. Chan, Reina Itakura, Zhiyuan Ma and Yuancheng Yu posted [arXiv 2611.06813](https://arxiv.org/abs/2611.06813). They give two different, short algorithms that solve 4-hyperclique in 3-uniform hypergraphs in truly subquartic time. The first, with exponent 3.957, reduces the problem to counting colour-alternating 4-cycles and uses anti-commuting matrix families. The second is shorter and works directly with formulas. Neither needs a new algorithm for the generalized 3-wise matrix product. The paper says: "We have actually found two different proofs of the result (both using AI)!"

AI disclosure (verbatim): "Both proofs in this paper are obtained using ChatGPT Sol 6.1, prompted by different suggestions. This manuscript is human-written … The authors verified the correctness and originality of all content, including references."

## Why it matters

The h-uniform hyperclique hypothesis was a standard assumption for conditional lower bounds. The paper lists applications to induced 4-cycles, Klee's measure problem, LCAs in DAGs, CSPs and geometric problems, and most of them use the h = 3 case. Those lower bounds now need other assumptions. No public reactions had been found as of 5 Nov (HN search: none).

## What is disputed or not yet verified

- Verification: Unrefereed preprint; authors verified correctness

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 189 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 128 days after its cutoff
- Gemini 4 Argon (training cutoff March 2026): 219 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 158 days after its cutoff

## Sources

1. [arXiv 2611.06813: The 3-Uniform Hyperclique Hypothesis is False](https://arxiv.org/abs/2611.06813) (arxiv.org, paper)

## Changes

- 2026-11-05 (filed): Created from the arXiv PDF

## Related

- 2026-11-04: [Huffman coding with unequal letter costs is NP-complete (Codex)](https://postcutoff.com/e/2026-11-04-huffman-unequal-letter-costs-np-complete-codex/index.md)