Toolset for supporting
lattice based numbersystem research
Péter Hudoba, Attila Kovács
Eötvös Loránd University, Budapest{peter.hudoba,attila.kovacs}@inf.elte.hu

Generalized Number Systems (GNS)
Given are●●●a lattice Λ in Rn
M : Λ → Λ such that det(M) ≠0 (base)0 ∈ D ⊆ Λ a finite subset (digit set)

Definition
The triple (Λ, M, D) is called a number system (GNS) if every element
x of Λ has a unique, finite representation of the form
x = d0+Md1+M2d2+ … +MLdL, where di ∈ D.
No loss of generality in assuming that M is integral acting on Λ = Zn

Radix System
If (Λ, M, D) is a number system then
1.
2.
3.

D must be a full residue system modulo M,
M must be expansive,det(In − M) ≠ ±1 (unit condition)

If a system fulfills the first two conditions then it is called a radixsystem

φ function
Denote the “get and drop the last digit” function with φ.
x ↦ M−1(x - d), where x ≡ d (mod M)

A (Λ, M, D) radix system GNS if and only if the only periodic point is 0.

We can construct a cover box that contains all of the periodic pointsof the dynamic system of φ.

Research problems
Given (Λ, M, D) decide the number system property.
●Deterministic approaches○ Examining the discrete dynamic (Covering method).
○●

Examining the carry propagation (Brunotte method).

Probabilistic approaches○○

Most of the points leads to the non-zero periodic point in manycases
Based on our conjecture we have a big speedup

Given (Λ, M, D) determine all the cycles●Finding the non-zero periodic points (witnesses)

Research problems - complexity
The algorithmic complexities of the previous problems are unknown.
Computer experiments show that they have exponential timecomplexities.

numsys.info●

Download actual version oftoolset in Sage or in Python
○○○

●
●
●

Contains readme withinstalling details
Many of examples
Doxygen documentation

Download example inputs
Collection of relevantpublications
Candidate databaseToolset
We implemented a Python (NumPy and SymPy) and Sage based
system that contain the following:●●●

Procedures for the decision and the classification problems;
Visualization for structure analysis, fractions, etc.
Different optimization algorithms, etc.

Toolset - getting started

Creating a radix system with thefollowing base and digit set:

Examplers = RadixSystem([[0,-3],[1,2]],[[0,0],[1,0],[2,0]])Base:print(rs.isGNS())

0-3

12

Result:FalseDigit set:
012

000

Toolset - digit set generators
Examplers = RadixSystem([[0,-7],[1,-7]],
RadixSystemCanonicalDigits())
print(rs.getDigits(),rs.isGNS())

Examplers = RadixSystem([[0,-7],[1,-7]],
RadixSystemSymmetricDigits())
print(rs.getDigits(),rs.isGNS())([[0, 0], [1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6,0]], True)([[-3, 0], [-2, 0], [-1, 0], [0, 0], [1, 0], [2, 0],[3, 0]], False)

Predefined generators:
●
●
●
●
●

RadixSystemSymmetricDigits
RadixSystemCanonicalDigits
RadixSystemShiftedCanonicalDigits
RadixSystemAdjointDigits
RadixSystemDenseDigits

Toolset - finding witnesses
rs = RadixSystem([[0,-7],[1,-7]],
RadixSystemCanonicalDigits())[[[0, 0], [0, 0]]]

print(rs.getCycles())[[[12, 2], [-12, -2], [12, 2]], [[6, 1],[-6, -1], [6, 1]],[[0, 0], [0, 0]],[[-18, -3], [18, 3], [-18, -3]]

rs = RadixSystem([[0,-7],[1,-7]],
RadixSystemSymmetricDigits())
print(rs.getCycles())]

Using the toolset - Drawing
rs = RadixSystem([[0,-3],[1,2]],RadixSystemCanonicalDigits())
dr = RadixSystemDrawer()g = dr.getPhiOrbitGraph(rs)g.save("test.svg",figsize=16)

Using the toolset - Drawing
rs = RadixSystem([[0,-7],[1,-7]],
RadixSystemCanonicalDigits())
dr = RadixSystemDrawer()g = dr.getFractionsSetPlot(rs)g.save("test.svg",figsize=16)

Smart decide function
1) If the box is small just do it2) Find periodic points directly
1 length cycles:●●

M-1(x-d)=x ⇒ x=(I-M)-1d
If is there is a d digit where the x is a lattice element then we
have found a cycle

2 length cycles:●●

M-1(M-1(x-d1)-d2)=x ⇒ x=(I-M2 )-1(Md2+d1)
If is there are d1 and d2 digits where the x is a lattice element
then we have found a cycle

Smart decide function
1) If the box is small just do it2) Find periodic points directly
3) Randomization method
4) Volume and phi runtime optimization method

Clearly the 2. and 3. steps are good for non-GNS cases, so the smart
decide doesn’t have speed up in GNS cases compared to thetwo-transform approach (if we only use the step 4).

Smart decide function

Candidate database●●●●

Search for candidates
Get properties
More than 10.000
candidates
Properties:○○○○○○○

volume,
GNS property,periodic points/cycles,eigenvalues/eigenvectors,signature,basinSizes,attractors positions.

Public API
result = callServer("http://numsys.info/radix-system/list",{".volume":">1000”,".gns":"0"})for i in result :rs = RadixSystem(i["base"],i["digits"])
print(rs.smartDecide())

Thank you forattiention!

Feel free to contact us if you haveany feedback or idea!

1. Kovács, A., On computation of attractors for invertible expanding linear
operators in Z k , Publ. Math. Debrecen, 56/1–2, (2000), 97–120.
2. Kovács, A., On number expansions in lattices, Math. and Comp. Modelling, 38,(2003), 909–915.
3. Burcsi, P., Kovács, A., Papp-Varga, Zs., Decision and Classification Algorithms
for Generalized Number Systems, Annales Univ. Sci. Budapest, Sect. Comp., 28,(2008), 141–156.
4. Hudoba, P., Kovács, A., Some improvements on number expansion
computations, Annales Univ. Sci. Budapest, Sect. Comp., 46, (2017), 81–96.

peter.hudoba@inf.elte.hu
attila.kovacs@inf.elte.hu