Pith Number

pith:BVSMKMZA

pith:2026:BVSMKMZAD7XVPEJZFK5JKVHUXT

not attested not anchored not stored refs resolved

On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic

Emil Rugaard Wieser, Jo\"el Ouaknine, Joris Nieuwveld, Madhavan Venkatesh, Mihir Vahanwala, Piotr Bacik

The first-order theory of single-variable Presburger arithmetic expanded by perfect fixed powers or degree-at-most-three polynomials is decidable.

arxiv:2605.16985 v1 · 2026-05-16 · cs.LO

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{BVSMKMZAD7XVPEJZFK5JKVHUXT}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

In the case of single-variable theories, we obtain positive results for the following two families of predicates: (i) for perfect fixed powers, decidability of the corresponding theory follows from the solvability of hyperelliptic Diophantine equations; and (ii) for polynomials of degree at most three, we establish decidability by relying on the low genus of the resulting algebraic curves.

C2weakest assumption

The logical decidability transfers directly from the solvability of the associated hyperelliptic Diophantine equations or from the low genus of the algebraic curves produced by the polynomial predicates (abstract, paragraph beginning 'In the case of single-variable theories').

C3one line summary

Decidability is shown for single-variable Presburger expansions with fixed powers via hyperelliptic Diophantine solvability and with degree-at-most-three polynomials via low-genus curves, with hardness results when restrictions are removed.

References

61 extracted · 61 resolved · 0 Pith anchors

[2] Starchak , editor = 2025 · doi:10.4230/lipics.mfcs.2025.72

[4] The Complexity of 2023 · doi:10.4230/lipics.icalp.2023.112

[5] The American Mathematical Monthly , volume = 1996

[6] Primary cyclotomic units and a proof of

[7] Classical and modular approaches to exponential 2006

Formal links

1 machine-checked theorem link

Receipt and verification

First computed	2026-05-20T00:03:34.471495Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

0d64c533201fef5791392aba9554f4bcc7e88c52eeca2efbf6085982e1ff88c8

Aliases

arxiv: 2605.16985 · arxiv_version: 2605.16985v1 · doi: 10.48550/arxiv.2605.16985 · pith_short_12: BVSMKMZAD7XV · pith_short_16: BVSMKMZAD7XVPEJZ · pith_short_8: BVSMKMZA

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/BVSMKMZAD7XVPEJZFK5JKVHUXT \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 0d64c533201fef5791392aba9554f4bcc7e88c52eeca2efbf6085982e1ff88c8

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "5fea301183d0cef8068dab829f448ef11b62bae9fb6634a48abd4cf1b206670b",
    "cross_cats_sorted": [],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.LO",
    "submitted_at": "2026-05-16T13:11:32Z",
    "title_canon_sha256": "ecb4ee45dee16effed225d4701b81ee7c366464c7ad07ac044adac82f475dfef"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.16985",
    "kind": "arxiv",
    "version": 1
  }
}