Covering Set¶

Certify that every term of a modularly periodic integer sequence has a divisor from one finite prime set by covering every index class with a periodic divisibility congruence.

Version: v1 · 2026-08-30 · History
Domain-specific #: 1576
Origin domain: mathematics
Subdomain: number theory

Core Idea¶

A covering set, in the number-theoretic sense used here, is a finite set of primes that acts as a certificate for an infinite integer sequence: every term of the sequence is divisible by at least one prime in the set. The certificate becomes finite because divisibility of an exponential or recurrence sequence modulo a fixed prime is periodic. Each prime therefore covers one or more residue classes of term indices, and the union of those index classes must cover every index in scope.^[1]

For the standard sequence

\[ a_n=k b^n+\varepsilon,\qquad \varepsilon\in\{-1,+1\}, \]

a prime \(p\nmid b\) covers the indices \(n\equiv r\pmod m\) when

\[ k b^r+\varepsilon\equiv0\pmod p \quad\text{and}\quad b^m\equiv1\pmod p. \]

Then \(b^{r+tm}\equiv b^r\pmod p\), so \(p\mid a_{r+tm}\) for every integer \(t\geq0\). A collection of such congruences is complete only if their residue classes cover all permitted values of \(n\). If the terms are larger in absolute value than the covering primes, divisibility then proves that every term is composite. This converts an infinite term-by-term claim into a finite modular audit.

The three layers must be kept separate. The prime set is the reusable list of divisors. The index covering is the family of congruence classes assigning every exponent to at least one divisor. The sequence-specific compatibility is the modular equation that makes each assignment true for the chosen \(k,b,\varepsilon\), or for the chosen recurrence and initial conditions. A list of primes without the latter two layers is not a covering set for the sequence.

Covering sets are especially associated with Sierpiński and Riesel constructions. Sierpiński proved in 1960 that infinitely many odd \(k\) make every \(k2^n+1\) composite by combining a complete system of exponent congruences with compatible congruences on \(k\).^[2] Selfridge's classical \(k=78557\) certificate uses the seven primes \(\{3,5,7,13,19,37,73\}\); the exact residue assignments are reproduced below.^[1] The same architecture also appears in primefree linear-recurrence constructions, where periodic zero positions modulo selected primes cover every term index.^[3]

This entry concerns that finite-prime, all-indices certificate. It does not use “covering set” for arbitrary geometric covers, set cover problems, topological covers, covering codes, or a bare covering system of congruences.

Structural Signature¶

Sig role-phrases:

the indexed integer sequence — a declared family \((a_n)\) and an exact index domain, usually \(n\geq0\) or \(n\geq1\)
the finite prime witness set — a finite collection \(P=\{p_1,\ldots,p_s\}\) of candidate divisors
the modular period for each prime — an order or recurrence period \(m_i\) after which the relevant sequence residues modulo \(p_i\) repeat
the covered index classes — congruences \(n\equiv r_i\pmod{m_i}\), possibly with several classes assigned to one prime
the local divisibility implications — proofs that every index in an assigned class yields \(a_n\equiv0\pmod{p_i}\)
the complete index cover — the union of assigned residue classes contains every index in the declared domain; overlap is allowed
the nontrivial-factor check — the divisor is proper for every covered term, so divisibility licenses compositeness rather than merely equality with the divisor
the universal inference — finite verification of periods, assignments, and coverage yields the conclusion that every sequence term has a divisor in \(P\)

The locked structural signature is

\[ \text{sequence specification} +\text{finite prime set} +\text{periodic divisor classes} +\text{complete index coverage} +\text{proper-factor check} \Longrightarrow \text{all-terms divisibility certificate}. \]

Recognition test: state the index domain, exhibit a finite prime set, attach to each prime the periodic index classes on which it divides, and reduce the union of those classes modulo a common multiple of their periods. If any residue remains uncovered, any local congruence fails, or a covered term can equal its assigned prime, the proposed certificate does not yet instantiate a covering set.

What It Is Not¶

Not an arbitrary finite set of primes. Relevance, small size, or frequent empirical divisibility does not suffice; every index must have a proved assignment.
Not merely a covering system. A covering system is a finite family of congruences covering all integers. A covering set adds sequence-specific primes and a valid divisibility implication for each congruence.^[1]
Not necessarily a partition. Index classes may overlap. Selfridge's certificate assigns \(n\equiv1\pmod4\) to 5 and \(n\equiv1\pmod3\) to 7, so indices such as \(n=1\) have more than one available divisor.
Not the resulting primefree or all-composite sequence. The sequence is the object certified; the covering set is the finite witness mechanism.
Not a proof that the listed primes are the only divisors. It gives at least one divisor from a bounded set for each term and says nothing exhaustive about the rest of the factorization.
Not a proof from sampled terms. Checking the first million terms cannot replace a complete periodic coverage argument unless the checked window is proved to contain a full common period and each modular implication is established.
Not an unrestricted use of “covering set.” In topology, combinatorial optimization, geometry, and coding theory the same words name different objects with different validity conditions.
Not guaranteed to be minimal or irredundant. Removing a prime may or may not open an uncovered residue class; minimality is a separate optimization property.

Scope of Application¶

The home domain is elementary and computational number theory of exponentially growing or periodically reducible integer sequences.

Sierpiński sequences: certify that \(k2^n+1\) is composite for every index by a finite collection of small prime divisors.
Riesel sequences: apply the corresponding construction to \(k2^n-1\), with sign-adjusted modular compatibility.
Other bases: replace 2 by \(b>1\); the period becomes the multiplicative order of \(b\) modulo each covering prime, provided \(p\nmid b\).
Primefree linear recurrences: exploit periodicity of recurrence states modulo primes so zero-position classes cover every sequence index. Jones and Somer use periodic modular cycles and covering systems in families of shifted binary recurrences.^[3]
Simultaneous constructions: choose parameter congruences by the Chinese remainder theorem so several sequences, powers, or sign variants inherit complete finite covers.^[1]
Computational search and optimization: enumerate candidate period patterns, solve compatibility congruences, test complete coverage, and minimize or strengthen the prime witness set.

The abstraction applies only when finite modular periodicity genuinely closes the infinite index domain. Some all-composite sequences have no known finite cover, and some constructions prove compositeness by algebraic factorization or other arguments instead. “Every term is composite” is therefore a broader outcome than “has a covering set.”

Clarity¶

A clear covering-set claim should be published as a certificate table rather than as a bare list. For every row record the prime \(p\), the index condition \(n\equiv r\pmod m\), the sequence-parameter congruence used, and the resulting divisibility statement. Then state a common modulus \(M=\operatorname{lcm}(m_1,\ldots,m_s)\) and verify all residues \(0,\ldots,M-1\). This exposes both possible defects: a bad row and a gap between rows.

Index conventions matter. A table covering all \(n\geq1\) need not cover \(n=0\), and a recurrence may begin at a different index. Sign and base matter as well: a certificate for \(k2^n+1\) is not automatically a certificate for \(k2^n-1\) or \(kb^n+1\). The phrase “same covering set” should therefore distinguish reuse of the prime list from reuse of the entire residue assignment.

The word “cover” is existential per index: at least one prime must work. It is not exclusive, and it is not a claim of unique factorization. The most concise honest statement is: “For every \(n\) in the stated domain, at least one row applies, and its prime is a proper divisor of \(a_n\).”

Manages Complexity¶

The covering set compresses an infinite universal claim into three finite objects: a bounded prime list, a bounded residue table, and a bounded common-period coverage check. Instead of factoring ever larger terms, the reasoner works in small residue rings. The certificate is auditable, portable between proof and computation, and cheap to recheck.

A practical construction loop is:

compute short multiplicative orders or recurrence periods modulo candidate primes;
determine which index residues make the sequence zero modulo each prime;
choose classes whose union covers a full common period;
solve any parameter congruences, often with the Chinese remainder theorem;
verify every local congruence and every residue of the common period; and
check that assigned divisors are proper on all exceptional small terms.

The standard diagnostics follow directly. A gap diagnostic enumerates uncovered residues modulo \(M\). A row diagnostic substitutes the row's least residue and checks the period relation. A redundancy diagnostic removes one prime or one class and reruns the coverage check. A domain diagnostic checks boundary indices and sign/base changes. Corresponding interventions are to add or replace a prime class, refine the common modulus, repair the parameter congruence, restrict the claim honestly, or handle finitely many exceptional terms separately.

The abstraction also prevents overwork. Once a finite cover is valid, no additional factor search is needed to prove non-primality of later terms. Conversely, if the goal is the actual factorization or the least prime factor of each term, the covering set is intentionally insufficient.

Abstract Reasoning¶

The key reasoning move is local-to-global through periodicity and coverage. Each prime supplies a local theorem on one arithmetic progression of indices. Completeness of the union upgrades those local theorems to a global quantifier over all indices. The proof is not induction: it does not propagate truth from \(n\) to \(n+1\). It quotients the infinite index set by a finite common period and checks representatives.

Formally, let \(I\) be the index domain and define a relation \(R\subseteq P\times I\) by \(pRn\) exactly when the certified modular rule gives \(p\mid a_n\). A covering set requires the projection of \(R\) onto \(I\) to be all of \(I\). Periodicity makes this infinite surjectivity check finite: if every row is periodic with period dividing \(M\), it is enough to check the \(M\) residue classes. This is why completeness of the index cover, rather than cardinality of the prime list, is the decisive invariant.

The construction direction reverses the proof direction. To verify a candidate \(k\), begin with \(k\) and test divisibility patterns. To generate infinitely many candidates, begin with a desired exponent cover, select a prime compatible with each modulus, impose congruences on \(k\), and invoke the Chinese remainder theorem. Sierpiński's original construction exemplifies this inversion from certificate design to parameter family.^[2]

Knowledge Transfer¶

The full abstraction transfers literally within number theory wherever an indexed integer sequence has finite modular state and selected primes cover all zero-position classes. The objects change—exponentials, sign variants, Lucas-type recurrences—but the proof obligations do not: compute periods, bind index classes to primes, cover the domain, and rule out trivial equality.

Useful knowledge transfers between Sierpiński/Riesel work and primefree recurrences. A researcher who sees a modular cycle can search its zero positions; who sees several zero-position progressions can ask whether they cover; who has a cover can solve parameter congruences rather than test parameters blindly. Jones and Somer's recurrence constructions explicitly exploit finite generic cycles modulo divisors and covering systems, showing that the method is not tied to \(k2^n\pm1\).^[3]

Outside number theory, the portable skeleton is merely Coverage / Reachability plus Periodicity: finitely many periodic mechanisms collectively reach every required target. That skeleton is useful, but calling a software-test suite or a rotating maintenance schedule a “covering set” would shed the prime-divisibility semantics that define this node. The domain-specific identity travels only while integers, modular divisibility, sequence indices, and proper-factor inference remain intact.

Examples¶

Canonical: Selfridge's covering set for \(78557\cdot2^n+1\)¶

For \(a_n=78557\cdot2^n+1\), use \(P=\{3,5,7,13,19,37,73\}\). Filaseta, Finch, and Kozek record Selfridge's seven implications as follows.^[1]

index class	assigned prime	modular check on \(78557\)
\(n\equiv0\pmod2\)	3	\(78557\equiv2\pmod3\)
\(n\equiv1\pmod4\)	5	\(78557\equiv2\pmod5\)
\(n\equiv1\pmod3\)	7	\(78557\equiv3\pmod7\)
\(n\equiv11\pmod{12}\)	13	\(78557\equiv11\pmod{13}\)
\(n\equiv15\pmod{18}\)	19	\(78557\equiv11\pmod{19}\)
\(n\equiv27\pmod{36}\)	37	\(78557\equiv6\pmod{37}\)
\(n\equiv3\pmod9\)	73	\(78557\equiv9\pmod{73}\)

For example, \(n\equiv27\pmod{36}\) gives \(2^n\equiv2^{27}\pmod{37}\), and the row asserts \(6\cdot2^{27}+1\equiv0\pmod{37}\); the order of 2 modulo 37 is 36, so the implication repeats. The least common multiple of the row moduli is 36. Direct enumeration of residues \(0,\ldots,35\) finds no gap: evens are covered by 3; the remaining odd residues are covered by the six other classes, with some overlap. Each term is larger than its assigned divisor, so every \(78557\cdot2^n+1\) is composite.

Mapped back: the indexed integer sequence is \(78557\cdot2^n+1\); the finite prime witness set has seven members; the modular periods divide 36; the covered index classes are the seven rows; the local divisibility implications are the row congruences; the complete index cover is the checked residue set modulo 36; the nontrivial-factor check holds because every term exceeds the assigned prime; and the universal inference is compositeness for all \(n\geq0\).

Applied / In Practice: designing an infinite Sierpiński family¶

Sierpiński's 1960 construction starts from a cover rather than from a single \(k\). Use the exponent classes

\[ 1(2),\ 2(4),\ 4(8),\ 8(16),\ 16(32),\ 32(64),\ 0(64), \]

where \(r(m)\) means \(n\equiv r\pmod m\). These classes cover every integer: an index is sorted by the exact power of 2 dividing it, with odd indices in the first class and multiples of 64 in the last. Assign the primes \(3,5,17,257,65537,641,6700417\), respectively. Impose \(k\equiv1\) modulo the first six primes and \(k\equiv-1\pmod{6700417}\). The local period congruences then force the applicable prime to divide \(k2^n+1\). The Chinese remainder theorem supplies an infinite arithmetic progression of odd \(k\) satisfying all parameter constraints, hence infinitely many Sierpiński numbers certified by the same cover architecture.^[2]^[1]

Mapped back: the indexed integer sequence is the parameterized family \(k2^n+1\); the finite prime witness set is chosen from Fermat primes and the two prime factors used for the final Fermat-number stage; the modular periods are the displayed powers of two; the covered index classes form a disjoint exhaustive cover; the local divisibility implications follow from the congruences on \(k\); the complete index cover is built into the 2-adic case split; the nontrivial-factor check is secured by taking sufficiently large positive solutions; and the universal inference applies simultaneously to every \(k\) in the resulting congruence class.

Structural Tensions¶

T1: Finite certificate versus infinite obligation. The appeal is that a bounded table settles infinitely many terms, but one missing residue invalidates the universal conclusion. Diagnostic: reduce all classes modulo their least common multiple and enumerate every residue, including the domain's boundary index.

T2: Local divisibility versus global coverage. Every row can be arithmetically correct while their union leaves gaps. Diagnostic: audit row validity and union completeness as two independent tests; neither can stand in for the other.

T3: Coverage versus partition. Overlapping classes provide redundant divisors and may simplify construction, while disjoint classes simplify explanation and minimality analysis. Diagnostic: do not reject overlap; record multiplicity separately and ask only whether every index is covered at least once.

T4: Existence versus proper-factor force. A listed prime can divide a term equal to that prime, which does not prove compositeness. Diagnostic: compare each exceptional small term with its assigned divisor or prove a uniform lower bound.

T5: Reusable prime list versus sequence-specific assignment. The same set of primes may participate in several constructions, but the residue classes and parameter congruences can change with base, sign, or initial values. Diagnostic: when reusing a list, recompute every modular implication rather than carrying over the word “cover.”

T6: Minimal cover versus robust cover. Removing redundant primes creates a smaller certificate, but overlap can make errors easier to detect and families easier to construct. Diagnostic: state whether the objective is proof, irredundancy, minimum cardinality, or multiple coverage before pruning.

T7: Domain-specific autonomy versus reduction to parent structure. Coverage / Reachability and Periodicity explain why a finite repeated relation can reach every index, but they do not supply primes, modular orders, divisibility, parameter congruences, or the proper-factor inference. Diagnostic: retain this node when those number-theoretic roles do proof work; reduce only an application that uses the generic periodic-coverage skeleton without modular divisibility semantics.

Structural–Framed Character¶

Covering Set is structural-leaning domain-specific. Its certificate is formal and observer-independent, but its identity is inseparable from number-theoretic vocabulary and validity conditions.

Evaluative weight: low; a cover can be correct or incorrect without carrying a normative judgment.
Human-practice-bound: no; the modular relations hold independently of anyone's conventions once the sequence and index domain are fixed.
Institutional origin: no; the pattern arises from arithmetic structure, not a social rule or organization.
Vocabulary travel: limited; “prime,” “divides,” “residue class,” “multiplicative order,” and “composite” must travel with the abstraction.
Import versus recognize: chiefly recognize; the certificate exposes periodic divisibility already present, although construction deliberately chooses parameters to create it.

Its structural parent skeleton is a finite family of periodic source-to-target relations whose union reaches every required target. Its domain frame fixes the sources as primes, the targets as sequence indices, the relation as divisibility, and the downstream verdict as an all-terms number-theoretic conclusion. Its character: formal and structural in operation, but irreducibly number-theoretic in identity.

Structural Core vs. Domain Accent¶

Skeletal structural core. A finite set of mechanisms each reaches a periodic subset of an infinite target domain; a common-period audit shows that their union is exhaustive; local guarantees then lift to a universal conclusion.

Indispensable domain accent. The mechanisms are prime divisors, target positions index an integer sequence, periodicity is modular, local guarantees are divisibility congruences, parameter families are assembled with tools such as the Chinese remainder theorem, and the terminal conclusion concerns proper factors and compositeness.

Why this is not a prime. Free substitution of targets and mechanisms preserves only periodic coverage. Replace primes with software tests or maintenance crews and the characteristic validity checks—multiplicative order, zero residues, proper divisors, base/sign compatibility—disappear. The parent skeleton transfers; the full recognition, diagnostic, and intervention package does not.

Covering Set instantiates Coverage / Reachability in a strict number-theoretic form: the required targets are all allowed indices, and each must be reached by at least one prime-divisibility rule. It presupposes Periodicity, because a finite residue table can govern infinitely many terms only when divisibility patterns repeat modulo each prime. Set and Membership supplies the generic collection apparatus but does not explain the certificate role. Partition is related only when the index classes happen to be disjoint; overlap is valid and common, so partition is not constitutive. Verification describes auditing the certificate, while Mathematical Induction is a contrast rather than the proof engine.

The closest domain-specific neighbor is Primefree Sequence. That node describes a class of recurrence sequences and its nontrivial all-composite condition. Covering Set describes one finite proof mechanism that can certify such a sequence and also applies to exponential families outside the Fibonacci-type class. Neither subsumes the other.

Relationships to Other Abstractions¶

Current abstraction Covering Set Domain-specific

Parents (2) — more general patterns this builds on

Covering Set is a kind of Coverage / Reachability Prime

Covering Set instantiates Coverage / Reachability in a strict number-theoretic form: the required targets are all allowed indices, and each must be reached by at least one prime-divisibility rule.
Covering Set presupposes Periodicity Prime

Covering Set instantiates Coverage / Reachability in a strict number-theoretic form: the required targets are all allowed indices, and each must be reached by at least one prime-divisibility rule.

Hierarchy paths (3) — routes to 3 parentless roots

Covering Set → Coverage / Reachability → Completeness

Show alternative paths (2)

Neighborhood in Abstraction Space¶

Covering Set sits in a sparse region of the domain-specific corpus (68^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Algebraic Structure & Reciprocity Theorems (5 abstractions)

Nearest neighbors

Primefree Sequence — 0.86
Wilf Equivalence — 0.85
Quartic reciprocity — 0.85
Structure Theorem for Finitely Generated Modules over a Principal Ideal Domain — 0.85
Field of fractions — 0.84

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Covering system of congruences. This is the index-side combinatorial component and need not carry any primes or sequence divisibility. Tell: Ask whether each congruence is paired with a prime that provably divides the sequence terms in that class.
Set cover. The optimization problem chooses subsets whose union covers a universe and has no intrinsic modular or divisibility semantics. Tell: Ask whether the objects being minimized are arbitrary subsets or prime-index congruence certificates.
Primefree Sequence. This is the certified sequence class, usually with recurrence and coprimality conditions, not the finite divisor witness. Tell: Ask whether the subject is the infinite sequence or the finite prime certificate attached to it.
Sierpiński number or Riesel number. These are parameter values \(k\) satisfying all-composite sequence properties; a covering set is a common but not logically defining proof route. Tell: Ask whether the named object is an integer parameter or a collection of divisors plus residue assignments.
Partition. A partition requires exactly one block per element, whereas covering residue classes may overlap. Tell: Find an index covered by two primes; if that is allowed, the structure is coverage rather than partition.
Finite factor base. A factor base is a chosen prime collection for algorithms such as sieving and need not divide every member of an infinite declared sequence. Tell: Demand the all-indices coverage proof.
Empirical factor table. A computed prefix can suggest a cover but does not settle later terms without proved periodic closure. Tell: Look for a common period and a complete residue audit rather than only a stopping bound.
Algebraic factorization. A formula such as \(x^{2r}-1=(x^r-1)(x^r+1)\) can prove a family composite without a finite set of prime divisors. Tell: Ask whether the proof provides recurring specific primes or only nonconstant symbolic factors.

References¶

[1] Michael Filaseta, Carrie Finch, and Mark Kozek, “On Powers Associated with Sierpiński Numbers, Riesel Numbers and Polignac's Conjecture”, Journal of Number Theory 128.7 (2008), 1916–1940; author-hosted full text. Verified 2026-08-26. Gives the definition of a covering system, reconstructs Sierpiński's construction, records Selfridge's exact seven congruence implications for 78557, and develops further covering-based families and boundaries. registry ↩a ↩b ↩c ↩d ↩e ↩f

[2] Wacław Sierpiński, “Sur un problème concernant les nombres \(k\cdot2^n+1\)”, Elemente der Mathematik 15 (1960), 73–74. Verified 2026-08-26. Primary source for the finite congruence construction proving that infinitely many odd parameters produce all-composite \(k2^n+1\) sequences. registry ↩a ↩b ↩c

[3] Lenny Jones and Lawrence Somer, “Primefree Shifted Binary Linear Recurrence Sequences”, The Fibonacci Quarterly 57.1 (2019), 51–67. Verified 2026-08-26. Primary source for recurrence families whose finite modular cycles and covering systems certify primefree shifted sequences, supporting the abstraction's recurrence habitat beyond \(k2^n\pm1\). registry ↩a ↩b ↩c