Cycle–T ee Po en ials o Colla z Residue G aphs
Equal-Slack Cycles, ε-Squeezed T ees, and a Conse a i e Excep ional Edge
Aleksanda Pe išić
Oco be 2025
Abs ac
This no e explains only how he ce i ica e
ϕ
o he accele a ed Colla z map is cons uc ed,
se ing as p epa a ion o a code implemen a ion. We wo k on he odd- esidue g aph modulo
2
k
and de ine pe -edge weigh s om he 2-adic alua ions
2
(3
+ 1). On each di ec ed
cycle we impose equal slack, which uniquely ixes he cycle-wide slack by elescoping and
de e mines
ϕ
along he cycle a e ancho ing one e ex. Fo e e y in- ee eeding a cycle,
we assign a iny uni o m nega i e ee slack (“
ε
-squeezing”) and p opaga e
ϕ
ou wa d so
ha all ee inequali ies hold s ic ly. A he unique excep ional esidue
†
wi h 3
†
+ 1
≡
0
(
mod
2
k
), we en o ce a conse a i e slack (sligh ly below
−ln
2) o ha den he mos delica e
inequali y. Finally, we no malize
ϕ
by a single o se (e.g.
ϕ
(1) = 0) and speci y he expo
shape (
, ϕ
(
)
, 2
(3
+ 1)
,succ
(
)
, s
(
)) a ixed p ecision. The aim is exposi o y: o make he
cycle– ee assembly o
ϕ
, he ole o equal slacks, he
ε
-squeezed ees, and he conse a i e
excep ional edge ully explici so hey can be ep oduced e ba im in code.
1 Se ing and No a ion
Fix an in ege k≥1and le M= 2k. Conside he di ec ed g aph on he odd esidues
Rk={ ∈ {1,2,...,M −1}: ≡1 (mod 2) },
wi h one ou going edge pe node
succ( ) = Fk( ) := odd(3 + 1) mod M,
whe e
odd
(
n
) emo es all powe s o 2 om
n
. Thus each node has exac ly one successo and he
g aph is a disjoin union o di ec ed cycles wi h in-a bo escences (in- ees) eeding hose cycles.
Fo each ∈ Rkde ine
w( ) = ln 3 − 2(3 + 1) ln 2+ρ+δ, ρ := bln 2 −ln(1 −p) + ζ, (1)
whe e
2
is he 2-adic alua ion and
b, p, ζ, δ
a e ixed cons an s. A ce i ica e is a po en ial
unc ion ϕ:Rk→Rsa is ying he di e ence cons ain s
ϕ( )≥ϕ(succ( ))+w( ) (∀ ∈ Rk).(2)
I is o en con enien o eco d he slack o each inequali y,
s( ) := w( ) + ϕ(succ( )) −ϕ( )≤0.
Feasibili y o ϕis equi alen o s( )≤0 o all .
1
2 Equal-Slack on Cycles
Le
C
=
{ 0, 1, . . . , L−1}
be a di ec ed cycle (indices modulo
L
), so
succ
(
i
) =
i+1
. Suppose
we impose equal slack sCon each cycle edge and eplace (2) by he equali ies
ϕ( i)−ϕ( i+1) = −w( i)+sC, i = 0, . . . , L −1.(3)
Summing (3) o e i elescopes he le -hand side o 0, hence
0 = −
L−1
X
i=0
w( i)+L sC⇒sC=1
LX
i∈C
w(i).
Thus he cycle slack is uniquely ixed by he edge weigh s. Choose an ancho e ex
∗∈C
and
se
ϕ
(
∗
)=0; hen all
ϕ
on
C
a e de e mined by chaining
(3)
. Since
sC
is ypically nega i e,
he cycle cons ain s hold wi h a uni o m nega i e ma gin and he e o e emain easible.
3ε-Squeezed T ees
Conside an edge
u→
in a ee eeding in o a cycle (so
=
succ
(
u
)is al eady assigned). To
ep oduce a nea -equali y p o ile while keeping easibili y s ic , assign a small uni o m nega i e
ee slack s ee <0(e.g. s ee =−10−6) and se
ϕ(u) = ϕ( )+w(u)−s ee.(4)
Then he co esponding slack is exac ly
s
(
u
) =
s ee ≤
0. Applying
(4)
ecu si ely om he
cycle ou wa d assigns
ϕ
o e e y node in each in- ee, wi h all ee edges ca ying he same iny
nega i e slack.
4 The Excep ional Residue
The e is a unique excep ional esidue
†
such ha 3
†
+ 1
≡
0 (
mod M
). Fo his edge, a
dis inguished nega i e alue close o
−ln
2na u ally appea s. To build in a obus sa e y ma gin
(independen o loa ing-poin oundo ), se a conse a i e excep ional slack
s( †) = −ln 2 −10−6,(5)
and en o ce equali y
ϕ
(
†
) =
ϕ
(
succ
(
†
)) +
w
(
†
)
−s
(
†
). This makes he excep ional inequali y
s ic ly s onge by 10−6 han he exac −ln 2 a ge , ensu ing s( †)≤0wi h a iny bu e .
5 No maliza ion and Fo ma ing
Adding a cons an o ϕp ese es all slacks. One may he e o e no malize by ixing
ϕ(1) = 0,(6)
wi hou a ec ing easibili y. Fo nume ical epo ing, one can expo
, ϕ( ), 2(3 +1),succ( ), s( )
wi h ixed decimal p ecision o ϕand s(e.g. 12 places), and in ege ields o esidues and 2.
2
6 Why Feasibili y Is P ese ed
Feasibili y equi es s( )≤0 o all .
•
On cycles,
sC
is de e mined by he exac iden i y
Pi∈Cϕ
(
i
)
−ϕ
(
i+1
)
= 0; he induced
alue is ypically nega i e, hence s( )=sC≤0on all cycle edges.
•On ees, (4) en o ces s(u)=s ee <0, so each ee inequali y holds s ic ly.
•A he excep ional esidue, (5) se s s( †)<0by design, also s ic .
•The no maliza ion (6) is a global shi o ϕand does no change any slack.
Consequen ly, he cons uc ed
ϕ
sa is ies
(2)
e e ywhe e. The (delibe a ely) nonze o nega i e
slacks se e as a conse a i e bu e , making he ce i ica e obus agains ini e-p ecision
a i hme ic and mino implemen a ion di e ences.
7 Algo i hmic Ou line
1. Build he unc ional g aph 7→ succ( )and he weigh s w( ) om (1).
2. Decompose he g aph in o cycles (wi h s anda d o oise–ha e o s ack-based DFS).
3. Fo each cycle C, compu e sCand sol e (3) a ound Cwi h ϕancho ed a one node.
4. P opaga e (4) ou wa ds along each in- ee wi h s ee =−10−6.
5. A he excep ional esidue †, use (5) ins ead o s ee.
6. No malize by ϕ(1) = 0 and expo ( , ϕ, 2,succ, s)a ixed p ecision.
(see [1])
Re e ences
[1] A. Pe isic. A Lyapuno Ce i ica e o he Accele a ed Colla z Map. Zenodo, 2025.
3
