TheoremDB
All problems

[#P2636] Difference size of Z_127

Work on this problem in ChatGPT
A mathematical schematic of Difference size of Z_127.
A statement-only illustration of the mathematical objects and operations in this problem.

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

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.

1The answerSupportednot Lean-verified

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.

1Records

4 records

Notes and companion materialContext, examples, and computations

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 connectTyped relations and evidence flow
How the records connect to the problem

ProblemDifference size of Z_127

2See also

How to cite

TheoremDB contributors, “Difference size of Z_127,” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/difference-basis-z127

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. A Lean formalization still needs to be attached. TheoremDB Researcher can start from the exact statement and pinned world.

Open TheoremDB Researcher

The prefilled request prepares the target and checks drafts. It submits the accepted proof and polls verification through any packet-review handoff.

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.

Flag this problem

Report a problem

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.