PaperlayerView exact revision on arXiv

Source-linked AI summary

Signed p-adic Residual Encodings of Finite-Domain All-Different Systems with a Sudoku Case Study

Greg Baker

arXiv:2609.16063v1cs.LG

TL;DR

The paper asks how signed p-adic residual objectives can encode finite-domain constraints, extending work focused on positive weights. It gives a compiler and a domination theorem that place minimisers in the finite domain, yielding minimum-conflict or satisfying assignments and a Sudoku case study.

  • Problem

    How can signed p-adic residual objectives encode finite-domain constraints, given prior work focused on positive weights?

    Source: §1 · p. 1

  • Method

    The compiler combines positive rows that pin coefficients to allowed values with bounded negative rows that reward inequality or clause satisfaction; coordinatewise domination places minimisers in the finite domain.

    Source: §1 · pp. 1, 3

  • Results

    All-different systems admit polynomial-time encodings whose global minimisers are domain-respecting minimum-conflict assignments, and, when satisfiable, exactly the satisfying assignments.

    Source: §10 · p. 19

  • Takeaways & Limitations

    For clauses of width less than p, a signed term can compactly represent the forbidden affine complement and reward clause satisfaction.

    Source: §10 · p. 19

    The all-different theorem uses the binary case needed by the construction.

    Source: §4 · p. 8

Abstract

from arXiv · show

We study signed, weighted affine $p$-adic residual objectives as native encodings of finite-domain constraints. For primes that separate the finite alphabet, sufficiently weighted positive unary rows pin each coefficient to its allowed set, while negative rows reward unequal endpoints or clause satisfaction. A coordinatewise domination theorem places every global minimiser in the finite domain; there the loss is, up to an additive constant, the all-different conflict count or the negative number of satisfied CNF clauses. Standard Sudoku provides an $81$-coefficient case study without a one-hot lift. A client-side implementation exposes the generated dataframes, arithmetic, diagnostics, and searches.

1 Introduction

The introduction presents signed p-adic residual objectives as a way to encode finite-domain constraints: positive rows pin coefficients to allowed values, while bounded negative rows reward inequality or clause satisfaction. A domination theorem places global minimisers in the finite domain, where the loss captures conflicts or satisfied clauses.

1 Introduction

  • Unlike ordinary least squares, finite signed p-adic objectives remain bounded because affine residual norms over Zp are at most one.Negative rows therefore act as bounded rewards, whereas sufficiently weighted negative rows can destroy boundedness over R.Source: §1 · p. 1, §2 · p. 4
  • Positive unary rows and coordinatewise domination place every global minimiser in the finite domain, where the loss represents all-different conflicts or satisfied clauses.For satisfiable instances, the minimisers are exactly satisfying assignments; otherwise they are domain-respecting minimum-conflict assignments.Source: §1 · pp. 1, 3
  • The clause compiler proves signed p-adic linear regression NP-hard for the threshold problem at the fixed prime p = 5.The reduction is stated in Corollary 5.Source: §1 · p. 1
  • The paper gives polynomial-size positive-only complement expansions for negative CNF and pairwise all-different rows, enabling diagnostic comparison with Mihara’s digitwise equality regression.The signed rows are retained for valuation and loss reporting.Source: §1 · p. 3
  • The Sudoku case study uses the native 81-cell digit space and includes a failed powers-of-two encoding and a client-side browser implementation.The implementation exposes generated dataframes, loss arithmetic, diagnostics, and searches.Source: §1 · p. 3

2 Preliminaries

  • For distinct integers from 1 through q with q < p, the p-adic residual norm is a zero-or-one indicator of inequality.The introduction frames the construction as compiling constraints into observations, with positive wells pinning coefficients to finite domains.Source: §1 · p. 3, §2 · p. 4

3 Worked examples

The worked examples demonstrate how signed residual objectives encode list-colouring and CNF constraints, then extend the Boolean example to general false labels. In each construction, domain-pinning rows constrain coefficients while negative rows reward constraint satisfaction.

3 Worked examples

  • The section demonstrates mechanical construction on small list-colouring and CNF instances before presenting the general theorems.The list-colouring example assigns x = (1, 2, 3), respecting domains and making every edge unequal.Source: §3 · p. 4, §3.1 · p. 4

3.1 An example

  • The toy list-colouring minimum-loss vectors are valid assignments, including the recovered regression optimum x = (1, 2, 3).Positive rows of weight 3 pin each coefficient, while rows of weight −1 reward unequal endpoints.Source: §3.1 · p. 5

3.2 p-adic linear regression can express CNF statements as well

  • The unique minimum has coefficients x = (0, 0), decoding to the satisfying assignment z1 = z2 = true.On Boolean coefficients, the wells contribute 6 and the loss is 6 − satΦ(x).Source: §3.2 · p. 6

3.3 General false labels

  • False labels may be any p-adic integers congruent to 1 modulo p; distinct labels bi = 1 + p 2^i let residuals identify exactly which clause literals are satisfied.The residual’s residue modulo p gives the number of satisfied literals, while the quotient’s binary expansion gives their identities.Source: §3.3 · pp. 6–7

4 A general all-different residual-objective template

Theorem 1 gives conditions under which signed p-adic objectives confine global minimisers to finite allowed domains, where the loss becomes a finite signed interaction objective. The construction characterises minimum-conflict assignments and extends to all-different systems and Boolean clause maximisation.

4 A general all-different residual-objective template

  • Under Theorem 1’s pinning and residual assumptions, every global minimiser lies in the finite domain, where the loss is a constant plus signed interaction terms.The theorem requires allowed values pairwise incongruent modulo p and each interaction residual on the domain to be zero or a p-adic unit.Source: §4 · p. 7
  • The same objective on Qp remains bounded below, attains its global minimum on D, and has no global minimiser outside D.Coordinates outside Zp are first snapped into Zp, then into D.Source: §4 · p. 8
  • The explicit list-colouring dataset uses one positive observation per allowed value and one negative observation per edge, with construction time O(Σ_i |D_i| + |E|).The positive observations pin coordinates; the negative observations reward inequality across edges.Source: §4 · pp. 8–9
  • The theorem is stated for simple graphs with binary edge weights; a weighted-edge version requires pinning weights above each vertex’s total incident edge weight.The binary case is the one needed for this construction.Source: §4 · p. 8

4.1 Correctness

  • The synthetic reduction’s global minimisers are exactly domain-respecting assignments with minimum edge-conflict count, and are proper list-colourings when the instance is satisfiable.The construction uses positive unary observations to pin allowed values and negative edge observations to reward unequal endpoints.Source: §4 · p. 9, §4.1 · p. 10
  • Any finite-domain all-different system can be compiled in polynomial time so its global minimisers are exactly its domain-respecting minimum-conflict assignments.When the system is satisfiable, these minimisers are exactly its satisfying assignments.Source: §4.1 · p. 11
  • Replacing p-adic residual norms with the discrete metric preserves the snapping result and the conclusions of Theorem 3 and Corollary 4.The p-adic construction remains the main case because it realises the indicator behaviour within the paper’s affine p-adic regression framework.Source: §4.1 · p. 11
  • For CNF clauses, negative observations reward satisfaction, and global minimisers maximise the number of satisfied clauses on Boolean assignments.The 3-CNF specialisation assumes p > 3.Source: §4.1 · p. 12

General false labels.

The paper extends signed clause encodings to arbitrary false labels and contrasts their bounded p-adic behavior with two obstacles to exact pinning over the reals. It also establishes NP-hardness for signed affine p-adic residual minimisation at the fixed prime 5.

General false labels.

  • False Boolean labels may be any b_i ≡ 1 (mod p), preserving the snapping and domination arguments while allowing residuals to identify satisfied literals.Using b_i = 1 + p 2^i leaves the loss landscape unchanged while making each residual identify its clause’s satisfied literals.Source: General false labels · p. 12
  • Signed affine p-adic residual thresholding is NP-hard at the fixed prime p = 5, and therefore global minimisation is NP-hard.The reduction encodes 3-SAT using p = 5 and pinning weight α = ∆ + 1.Source: General false labels · p. 12
  • For a clause with s literals, the signed form uses one negative row for its forbidden equality, while a positive complement encoding uses s observations.When p > s, the positive penalty distinguishes the forbidden value s from satisfying values 0 through s − 1.Source: General false labels · p. 13

4.2 Comparison with the Archimedean case

  • Over R, a sufficiently weighted negative row can make the quadratic objective unbounded below, so coordinatewise pinning weights do not ensure boundedness.The example has λ = 3 > γ = 2 yet its loss tends to −∞ along x1 = −x2 = t.Source: §4.2 · p. 13
  • Convex real penalties cannot pin a variable exactly to a finite non-singleton domain, and quadratic equality penalties require λ → ∞ for exactness.The Boolean unary well is minimised at the mean of {0, 1}, rather than at either domain value.Source: §4.2 · pp. 13–14
  • In Z_p, residual norms are bounded and unary wells attain minima exactly on their finite domains, enabling finite-weight domination; away from zero, residuals are locally constant.The same local constancy leaves p-adic losses without gradients, motivating random-walk rather than gradient dynamics.Source: §4.2 · p. 14

5 Unsatisfiable instances

For an unsatisfiable all-different system, global minimisers remain domain-respecting and minimise the number of conflicts. The same domination argument accommodates weighted constraints.

5 Unsatisfiable instances

  • For K3 with all lists {1, 2}, the global minimisers have exactly one conflict and loss 7 when λ = 3.No proper 2-colouring exists, so this is a minimum-conflict assignment.Source: §5 · p. 14
  • The unsatisfiable case is a Max-CSP regime: global minimisers are domain-respecting assignments with the least conflict count.The triangle example illustrates the general list-colouring characterisation.Source: §5 · p. 14
  • Weighted constraints yield a weighted minimum-conflict objective when each pinning weight exceeds the total incident edge weight.Replacing each unit edge reward with weight w_e > 0 preserves the domination argument.Source: §5 · p. 14

6 Sudoku as a special case

The paper applies its finite-domain construction to standard Sudoku, representing each cell with one coefficient and encoding clues and peer inequalities as signed residual terms.

6.1 Sudoku

  • Standard Sudoku is a list-colouring problem on 81 cells, with edges between cells sharing a row, column, or 3 × 3 box.Unclued cells have domain {1, . . . , 9}, while clue cells have singleton domains.Source: §6 · p. 14, §6.1 · p. 15

6.2 Positive pinning: snapping coefficients to digits

  • For every t in Zp, the unary well UD(t) is at least 8, attaining its minimum exactly when t belongs to the common domain D.Source: §6.2 · p. 15

6.3 Negative signed residual terms: rewarding inequality via p-adic norms

  • On the digit domain, a difference residual indicates inequality, and each cell has 20 distinct peers: eight row, eight column, and four additional box peers.These peer pairs encode the remaining row, column, and box constraints.Source: §6.3 · p. 15, Figure 3 · p. 16

6.4 Minimal and expanded residual objectives

  • The minimal objective has 729 − 8|C| positive observations and 810 negative observations, with α > 20 sufficient for domination.The expanded objective retains the nine digit wells on clue cells and adds separate clue pins; it requires α_clue > 20.Source: §6.4 · pp. 16–17
  • On the stated domain-respecting states, the remaining loss differs from deduplicated peer conflicts only by a constant, while heuristics use a duplicated column/box surrogate.The expanded-objective equivalence applies to digit-valued, clue-consistent states.Source: §6.4 · p. 17
  • With α > 20, every global minimiser of the minimal Sudoku objective is a clue-respecting digit assignment minimising peer conflicts.For a satisfiable puzzle, its global minimisers are exactly the valid completions; α = 21 is sufficient.Source: §6.4 · pp. 17–18

7 Representational parsimony

The Sudoku encoding uses one digit-valued parameter per cell rather than a one-hot lift, packaging the all-different structure into a scalar residual objective on 81 variables.

7 Representational parsimony

  • The p-adic construction uses 81 cell parameters instead of the 729 Boolean indicators in a standard SAT or exact-cover lift.This compares variable counts, not raw constraint counts.Source: §7 · p. 18
  • The signed construction packages Sudoku’s all-different structure into one residual objective on 81 cell variables.Its minimal form is a single scalar loss on that state space.Source: §7 · p. 18
  • The alternative powers-of-two encoding produced no successful solves on 50 benchmark puzzles, with local search repeatedly stalling on loss plateaus.That encoding uses one sum residual per row, column, or box.Source: §7 · p. 18

8 Computations with the induced p-adic loss

The computations compare two finite-state local-search methods on a small Sudoku sample and provide a browser-based view of the objective and search. Both methods completed the sampled puzzles, while row-swap search generally used fewer steps.

8 Computations with the induced p-adic loss

  • The greedy solver counts integer conflicts, while the Zubarev walk applies a Boltzmann transition to the same induced loss.On digit-restricted states, the relevant p-adic norms collapse to indicators, so integer conflicts suffice to compute the loss change.Source: §8 · p. 18
  • The Mihara-inspired diagnostic replaces each negative peer row with sixteen nonzero-difference equalities, but it solved none of the sample puzzles.It was not included among the 36 solver runs.Source: §8 · p. 18
  • Both methods completed all 18 puzzles; row-swap used fewer steps on 14 of the 18 paired puzzles.The sample comprises 36 successful method–puzzle runs; the authors describe these as proof-of-concept experiments, not a solver benchmark.Source: §8 · p. 18
  • 537.5, 2784, and 7040 median steps at 36, 30, and 26 clues, versus 4533.5, 8751.5, and 9911 for the Zubarev walk.The reported medians are for row-swap search and the Zubarev walk, respectively, at each listed clue count.Source: §8 · p. 18
  • The companion site displays a valid Sudoku completion, the 1,299-row objective summary, theoretical-floor equality, and zero-conflict result.The solver and experiment code are also available online.Source: Figure 4 · p. 19, §8 · p. 19

9 Related work

The paper situates its finite-domain objective among valued-CSP, Potts, and related discrete formulations, while distinguishing its signed affine construction from prior p-adic work. Its conclusion emphasizes finite-domain pinning, all-different conflict minimization, and a compact signed encoding of clause satisfaction.

9 Related work

  • The finite-domain objective is a valued-CSP or Max-CSP penalty, while pairwise inequalities preserve solutions but not matching-based propagation of global alldifferent.On finite domains, the list-colouring objective is also the zero-temperature antiferromagnetic Potts energy [6]; related problems map to Ising or QUBO objectives [7].Source: §9 · p. 19
  • The Sudoku heuristics use row permutations analogously to Lewis’s box-permutation simulated annealing, while standard formulations include exact cover, SAT, and alldifferent constraints [10].The paper specializes p-adic learning primitives discussed by Martins [15] to signed affine objectives that compile finite-domain constraints.Source: §9 · p. 19

10 Conclusion

  • Positive synthetic terms pin variables to a finite set, after which negative terms reward inequality or clause satisfaction.For all-different systems, global minimisers are domain-respecting minimum-conflict assignments, and in satisfiable instances they are exactly the satisfying assignments.Source: §10 · p. 19
  • After Boolean pinning, each clause narrower than p becomes a forbidden affine equality whose signed term rewards satisfaction; the signed form compactly represents the forbidden complement.Distinct false labels can identify satisfied literals without changing the loss landscape, but no optimisation or verification advantage is claimed for that labelling.Source: §10 · p. 19
  • The companion site lets readers trace Boolean CSPs from clauses to signed residual data and compile editable Sudoku into its objective and search.For Sudoku, the site displays the 1,299-row objective and search toward the theoretical floor.Source: §10 · p. 20

A Mihara’s digitwise regression and positive complement expansion

This appendix contrasts Mihara’s digitwise regression with positive-only expansions of finite-domain signed rows. It explains the expansion’s equivalence on the forced domain and notes that Mihara’s regression assumptions and termination properties do not directly match the synthetic Sudoku construction.

A Mihara’s digitwise regression and positive complement expansion

  • Mihara’s generalisation of Baker forcing and this paper’s result both pin finite domains, but use different hypotheses to control the remaining objective.The comparison is summarized in Table 6.Source: Table 6 · p. 20, A Mihara’s digitwise regression and… · p. 20
  • Mihara’s digitwise regression estimates c mod p^E recursively through modulo-p regression, residual subtraction, division by p, and restricted resampling [16].Its probability analysis assumes sufficiently large, random samples, low digitwise corruption, and suitable affine hulls at each digit step.Source: A Mihara’s digitwise regression and… · p. 20
  • The published procedure is not worst-case polynomial-time and may not terminate; one reported D = 100, r = 0.1 run remained unfinished after 1,700 initialisations.The analysis gives expected behaviour under its sampling, affine-hull, and noise assumptions, not a polynomial termination guarantee for arbitrary data.Source: A Mihara’s digitwise regression and… · pp. 20–21
  • Those regression assumptions do not directly fit Sudoku, where exact synthetic constraints act on cell values rather than observations from a hidden affine response law.The construction has no naturally sampled response vector, hidden coefficient vector, or assumed large noise-free affine locus.Source: A Mihara’s digitwise regression and… · p. 21
  • On the forced finite domain, replacing a negative row by positive rows for all attainable values except its forbidden target preserves minimisers, differing only by a constant.When distinct attainable values remain distinct modulo p, the forbidden target contributes |S| − 1 positive rows, while an allowed value makes exactly one complementary row vanish.Source: A Mihara’s digitwise regression and… · p. 21
  • For clauses, the positive complement expansion is polynomial-size and gives a positive-only weighted-consensus dataset in which satisfied clauses contribute inlier weight.The original signed row is retained for reporting its residual, norm, and signed loss contribution.Source: A Mihara’s digitwise regression and… · p. 21
  • For a Sudoku peer row, p = 19 separates the sixteen nonzero differences, so an unequal pair satisfies exactly one complementary equality and an equal pair none.The expansion lists xi − xj = s for the sixteen nonzero s in {−8, …, 8}.Source: A Mihara’s digitwise regression and… · p. 21
  • The website’s Mihara modes select fits by positive-consensus loss but audit them with the signed objective, continuing fresh starts until constraints are met or the user stops.The procedure is presented as an unbounded-restart heuristic, not a polynomial-time solver.Source: A Mihara’s digitwise regression and… · p. 21

B.1 Row-swap local search

The appendix describes a row-swap greedy search and a discrete Zubarev walk on clue-consistent Sudoku states whose rows remain permutations. The trace illustrates local updates, while the finite stochastic adaptation is explicitly not covered by Zubarev’s convergence guarantee.

B.1 Row-swap local search

  • The row-swap loss counts column and box conflicts, duplicating pairs that conflict in both; the seed-0 state has 47 deduplicated conflicts but Hcb = 56.Each row remains a permutation, so its row-conflict contribution is identically zero and omitted.Source: §B.1 · p. 22
  • The greedy search initializes clue-consistent row permutations and applies within-row swaps that reduce Hcb; only the two columns and their boxes can change.This row-based state space follows the metaheuristic design of Lewis, with rows rather than boxes as the permutation unit.Source: §B.1 · p. 22

B.2 Trace on a standard puzzle

  • The standard-puzzle trace starts from a seed-0 filling with 56 column/box conflict pairs and reaches a full solution after 227 swaps.Figure 5 shows the example puzzle; Table 7 records the first eight swaps.Source: §B.2 · pp. 22–23, Figure 5 · p. 23, Table 7 · p. 24

B.3 A discrete Zubarev walk

  • Zubarev’s continuous-space result gives a regime where expected loss strictly decreases under mild conditions, including a nonzero measure of improving moves.The paper introduces the discrete finite-move process as a random walk on row swaps.Source: §B.3 · pp. 23–24
  • The finite Sudoku heuristic has no claimed supermartingale or convergence guarantee because its state space and move measure differ from Zubarev’s setting.The Boltzmann weights serve only as a motivated move-selection rule.Source: §B.3 · p. 24
  • The discrete Zubarev walk samples row swaps with Boltzmann weighting based on the change in Hcb, using an annealing schedule that shifts from exploration toward exploitation.As βt approaches zero the rule becomes uniform random swapping; as βt grows it concentrates on the best loss-decreasing swap.Source: §B.3 · pp. 23–25

B.4 Zubarev trace on the standard puzzle

On paired, randomly carved Sudoku puzzles, both heuristics solved every instance, with the row-swap method using fewer steps on most paired runs. The powers-of-two encoding, by contrast, failed to find valid completions in the archived search experiments and produced losses with little useful local-search signal.

B.4 Zubarev trace on the standard puzzle

  • The Zubarev walk solved the standard puzzle after 10,029 swaps on the same restart.It sometimes accepts loss-increasing or loss-neutral swaps early in the trajectory.Source: §B.4 · p. 25

C.1 Experimental setup

  • The puzzles were made by sampling solved grids and randomly removing entries, without checking uniqueness.Each method–puzzle pair had one solve seed; results are paired, but the sample is not difficulty-normalised and supports no inferential performance claim.Source: §C.1 · p. 26

C.2 Results

  • Both heuristics solved all 18 paired puzzles, and row-swap took fewer steps on 14/18 paired runs.The sample is small and supports no stronger algorithmic claims.Source: §C.2 · p. 26, Table 9 · p. 26

D Powers-of-two experiments

  • For each Sudoku unit, the powers-of-two alternative replaces pairwise penalties with a residual based on the sum of its encoded digits, optionally regularised to encourage allowed values and enforce clues.The unit target is 511.Source: D Powers-of-two experiments · p. 27
  • The archived experiments on 50 Project Euler puzzles found no valid completion with the powers-of-two encoding.The prime sweep covered 15 primes, as listed in Table 10.Source: D Powers-of-two experiments · p. 27, Table 10 · p. 28
  • When a move changes the residual by more than its current p-adic norm, it erases all accumulated valuation on that unit at once.For listed primes and p > 255, every move is a p-adic unit step, so a one-cell error can score like an arbitrary unit sum coprime to p.Source: D Powers-of-two experiments · p. 28
  • For p > 1793, the powers-of-two loss counts only exact unit-sum matches, and a move improves it only by making a unit sum exactly 511.At smaller primes, valuations can instead reward arithmetic congruences unrelated to correctness; at no prime does the term grade progress toward a permutation.Source: D Powers-of-two experiments · p. 29

Compliance with ethical standards

The article reports no studies with human participants or animals. It provides experiment code and data, and a browser-based demonstration exposes the construction and representative searches.

Compliance with ethical standards

Code and data availability

  • The Python heuristic implementation is publicly available, alongside experiment scripts, archived CSV data, and supporting files.The submitted source package includes puzzle seeds, trace files, and figure sources for Tables 9 and 10 and Figure 7.Source: Code and data availability · p. 30

Interactive demonstration

  • A browser-based demonstration runs the Sudoku and Boolean-CSP compilers, residual dataframes, objective evaluations, diagnostics, and representative searches client-side.The optional natural-language schema extractor requires a browser exposing the on-device Prompt API.Source: Interactive demonstration · p. 30
Loading 2609.16063v1…