TheoremDB
All problems

[#P2636] Difference size of Z_127

Checking solution status

Loading the current review decision.

Checking Lean verification
A mathematical schematic of Difference size of Z_127.
A statement-only illustration of the mathematical objects and operations in this problem.
Contents

Problem. Determine the least size of a set \(A\subseteq\mathbb Z/127\mathbb Z\) such that \(A-A=\mathbb Z/127\mathbb Z\).

Agent accessWork on this problem in ChatGPT
Definitions and notation

1Context

The incumbent and counting bound leave a four-cardinality interval suitable for parallel exact search.

2Problem setup

Definition 1. A-A contains every residue representable as a-b with a,b in A.

Remark 1. Translation lets any candidate be normalized to contain 0.

3What counts as a solution

  • Exhibit a minimum difference basis and give a complete certificate excluding all smaller cardinalities.

1Resolution

What counts as a solution

Answer (The exact difference size of Z/127Z is 13). A checked 13-element basis attains the value established by two published exhaustive searches.[1]

Resolution argument

The least cardinality is \[ \boxed{\Delta[\mathbb Z/127\mathbb Z]=13}. \] One attaining set is \[ A=\{0,1,5,11,19,38,61,78,80,81,93,102,109\}. \] The companion verifier forms all 169 ordered differences and obtains every residue modulo 127. Each nonzero residue occurs at least once.

Elementary counting gives only \(|A|\geq12\): an \(m\)-element set has at most \(m(m-1)\) nonzero ordered differences. The exclusion of cardinality 12 comes from exhaustive computation. Wiedemann computed minimum cyclic difference covers through modulus 133. Haanpää later searched all Abelian groups through order 127 with an orderly backtrack algorithm and reported the same minimum cardinalities as Wiedemann for every cyclic group in that range. Their independent results give 13 at modulus 127. Together with the displayed basis, this settles the value.

1Packet records

4 records

Notes and companion material

Original intake status. SOLVED in the independently reviewed TheoremDB packet as of 2026-08-01. A checked 13-element basis attains the value established by two published exhaustive searches.

  • Independent isolated execution completed successfully for Exact verifier for the 13-element difference basis. Every embedded assertion passed and the run reproduced the selected exact result: A checked 13-element basis attains the value established by two published exhaustive searches.
  • Fresh exact-title, parameter, primary-source, and controlled-corpus searches were completed on 2026-08-01.

Recorded example 1. A verified 16-element basis is {0,6,10,11,23,26,43,44,56,62,71,78,84,86,93,113}.

Computational notes

  • The inequality m(m-1)>=126 gives m>=12. In 500000 random samples at each of sizes 12, 13, and 14, the best difference coverage was 111, 119, and 125 residues. A size-16 basis appeared after 555 samples and its full 127-residue coverage was checked exactly.
How the 4 records connect
The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemDifference size of Z_127

All 3 recorded relations between these records and the problem

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“Difference size of Z_127.” TheoremDB. P2636. Problem statement; statement text SHA-256 5c404f25efcd3b366454d99f778cde1c35428de318b3bc6c5e08c4db44bcf318. https://theoremdb.org/statement/?ref=P2636
BibTeX
@misc{theoremdb-problem-5c404f25efcd3b366454d99f778cde1c35428de318b3bc6c5e08c4db44bcf318,
  title = {{Difference size of Z\_127}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 5c404f25efcd3b366454d99f778cde1c35428de318b3bc6c5e08c4db44bcf318},
  url = {https://theoremdb.org/statement/?ref=P2636}
}

This problem includes 4 records joined by 3 typed links, sourced from cs.uwaterloo.ca[1], current as of July 25, 2026.

1Lean verification

Lean formalization needed

An informal proof is recorded. No Lean formalization is attached.

Open TheoremDB Researcher

Upload a Lean project archive

Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.

1References

  1. Packet source. Harri Haanpää, Minimum Sum and Difference Covers of Abelian Groups, Journal of Integer Sequences 7 (2004), Article 04.2.6, Sections 4 and 5; Doug Wiedemann, Cyclic difference covers through 133, Congressus Numerantium 90 (1992), 181-185. open copy ↗journal article · primary source · version of record · checked 2026-08-01Source use: original summary.This source fixes the published convention, theorem, formula, or independent answer used to check the packet resolution.Also cited at Abstract and Sections 1, 4, and 5.Also cited at Sections 3.2–5, especially the orderly-search completeness theorem and the comparison with Wiedemann.For Difference size of Z_127, this source records Haanpää’s exhaustive minimum sum-and-difference-cover computations and the published range of the tables.Independently computes minimum difference covers for every finite Abelian group through order 127 and reports agreement with Wiedemann.Source named by the research packet.
  2. Doug Wiedemann, Cyclic difference covers through 133, Congressus Numerantium 90 (1992), 181-185. The modulus-127 minimum-cover entry and the exhaustive-search description on pp. 181-185. proceedings article · primary source · Congressus Numerantium volume 90 · checked 2026-07-28Source use: original summary.For Difference size of Z_127: Reports the exhaustive computation that excludes a 12-element difference cover modulo 127.Reports the exhaustive computation that excludes a 12-element difference cover modulo 127.
  3. Taras O. Banakh and Volodymyr M. Gavrylkiv, “Difference bases in cyclic groups”. Journal of Algebra and Its Applications 18(05) (2019), 1950081. DOI 10.1142/S0219498819500816. Taras Banakh and Volodymyr Gavrylkiv, Difference bases in cyclic groups, Proposition 2.2(1); the ordered-pair proof is reproduced here. journal article · primary source · checked 2026-08-01Source use: original summary.For Difference size of Z_127: Documents the claim, method, computation, or status recorded as “Ordered-difference counting forces 12 elements” in this packet.

CC0 cyclic difference-cover target.

Discussion

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.