Multi-Base Representations
andtheir Minimal Hamming Weight
Daniel Krenn(joint work in progress with Vorapong Suppakitpaisarn and Stephan Wagner)

May 24, 2018

This presentation is licensed under a Creative Commons
Attribution-NonCommercial-ShareAlike 3.0 Unported License.

Supported by theAustrian Science Fund (FWF),
project P28466.

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Multi-Base Representations
Representations
n=

X

α

α

α

dj p1 1j p2 2j . . . pmmj

jdigits dj out of digit set {0, 1, . . . , d − 1}bases p1 , . . . , pm
(multiplicatively independent integers ≥ 2)
nonnegative integers αijααα

all power-products p1 1j p2 2j . . . pmmj distinct

Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Multi-Base Representations
Representations
n=

X

α

α

α

dj p1 1j p2 2j . . . pmmj

jdigits dj out of digit set {0, 1, . . . , d − 1}bases p1 , . . . , pm
(multiplicatively independent integers ≥ 2)
nonnegative integers αijααα

all power-products p1 1j p2 2j . . . pmmj distinct?
Multi-Base Representations

Question
How good is the “best possible”(minimal Hamming weight)
representation of a number?
Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Motivation from Cryptography

calculatenP = P + · · · + P
as efficiently as possible(P group element, n ∈Multi-Base Representations

N0)

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Motivation from Cryptography
standard systems(e.g. binary, decimal, . . . )calculatenP = P + · · · + P
as efficiently as possible(P group element, n ∈Multi-Base Representations

N0)

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Motivation from Cryptography
standard systems(e.g. binary, decimal, . . . )calculatenP = P + · · · + P
as efficiently as possible(P group element, n ∈N0)more digits(e.g. base 2,
digits {−1, 0, 1})

Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Motivation from Cryptography
standard systems(e.g. binary, decimal, . . . )calculatenP = P + · · · + P
as efficiently as possible(P group element, n ∈N0)more digits

multi-bases(e.g. base 2,
digits {−1, 0, 1})(e.g. bases 2i 3j ,digits {0, 1})

Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Hamming Weightmulti-base representationsXααα
dj p1 1j p2 2j . . . pmmj
n=jdigits dj out of digit set {0, 1, . . . , d − 1}bases p1 , . . . , pm
(multiplicatively independent integers ≥ 2)

Hamming Weightnumber of dj 6= 0 in representation

Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Hamming Weightmulti-base representationsXααα
dj p1 1j p2 2j . . . pmmj
n=jdigits dj out of digit set {0, 1, . . . , d − 1}bases p1 , . . . , pm
(multiplicatively independent integers ≥ 2)

Hamming Weightnumber of dj 6= 0 in representation
Minimal Hamming Weightminimal among all multi-base representations of nwith the same bases and digit set“measures” efficiency of representation
Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Minimal Hamming Weight
Theorem (K–Suppakitpaisarn–Wagner 2018)
fix bases p1 , . . . , pm (m ≥ 2)
multiplicatively independent
fix digit set containing 1
there exist positive constants K1 and K2(U) each integers n has representation
with Hamming weightat most K1 logloglogn n(L) infinitely many positive integers nwith no representation
with Hamming weightless than K2 logloglogn nMulti-Base Representations,

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Some Properties
smallest numbers with given weight (bases 2, 3)
weightnumber

1
1

2
5

3
23

4
431

5
18431

6
3448733

71441896119

...
...

(sequence A018899 in the OEIS)
finding minimal expansion seems to be hard
compute approximation 2i 3j ≤ n(Berthé–Imbert 2009)

Multi-Base Representations≈
Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Number of Representations
Theorem (K–Ralaivaosaona–Wagner 2014)
fix bases p1 , . . . , pm (m ≥ 2)
fix digit set {0, . . . , d − 1}
number ofmulti-base representations Pn of nlog Pn = κ(log n)m+ C1 (log n)m−1 log log n+ C2 (log n)m−1+ O (log n)m−2 log log n
withm

log d Y 1κ=m!
log pi#

i=1

Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Distribution of the Hamming Weight
Theorem (K–Ralaivaosaona–Wagner 2014)
fix bases p1 , . . . , pm (m ≥ 2)
fix digit set {0, . . . , d − 1}
Hamming weight ofuniformly random
multi-base representation of n:N

Gaussian/normal distribution (as n → ∞)expectationµn =κ(d − 1)(log n)m + O((log n)m−1 log log n)d log dvariance
σn2 =Multi-Base Representations

κ(d − 1)(log n)m + O((log n)m−1 log log n)
d 2 log dDaniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Single-base Representations

p

n=

X

dj p αjjdigits dj out of finite digit set
integer base p ≥ 2

Hamming weightaverage order of magnitude is log nworst case (maximum) also log nminimal Hamming weightnumber of minimal representations(Grabner–Heuberger 2006)
compute minimal expansion(Phillips–Burgess 2004, Heuberger–Muir 2009)
Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Greedy Algorithm
Natural Greedy Algorithm
input integer nαm
add largest power-product p1α1 . . . pm
less or equal to nαmcontinue with n − p1α1 . . . pm

output
n=

X

α

α

α

dj p1 1j p2 2j . . . pmmjjMulti-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Greedy Algorithm
Natural Greedy Algorithm
input integer nαm
add largest power-product p1α1 . . . pm
less or equal to nαmcontinue with n − p1α1 . . . pm

output
n=

X

α

α

α

dj p1 1j p2 2j . . . pmmjjGreedy algorithm ⇒ minimal representation
smallest counter-example
41 = 22 32 + 22 + 1 = 25 + 32
Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

History & Related Work
Upper Boundnatural greedy algorithm with input nterminates after log n O
log log n
steps
bases 2, 3, generalizes to arbitrary multi-base of primes(Dimitrov–Jullien–Miller 1998)“On the maximal distance between integers
composed of small primes” (Tijdeman 1974)

Multi-Base Representations



Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

History & Related Work
Upper Boundnatural greedy algorithm with input nterminates after log n O
log log n
steps
bases 2, 3, generalizes to arbitrary multi-base of primes(Dimitrov–Jullien–Miller 1998)“On the maximal distance between integers
composed of small primes” (Tijdeman 1974)
bases 2, 3, 5 (Yu–Wang–Li–Tian 2013)
sharpness of bound for double-base expansions(Chalermsook–Imai–Suppakitpaisarn 2015)
Multi-Base Representations



Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Termination of Greedy Algorithm
Corollary (K–Suppakitpaisarn–Wagner 2018)
fix bases p1 , . . . , pm (m ≥ 2)
multiplicatively independent
natural greedy algorithm with
 input nterminates after O logloglogn n steps
bound is sharp
output contains only digits 0 and 1

Multi-Base Representations• • • ,

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Proof of Upper BoundApproximation by Power-products
there are positive constants C and κ with−κne −C (log n)αm≤ p1α1 . . . pm≤n≈Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Proof of Upper BoundApproximation by Power-products
there are positive constants C and κ with−κne −C (log n)αm≤ p1α1 . . . pm≤ntwo bases p and q multiplicatively independent
set λ = logp q and M = dlogq ne≈
Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Proof of Upper BoundApproximation by Power-products
there are positive constants C and κ with−κne −C (log n)αm≤ p1α1 . . . pm≤ntwo bases p and q multiplicatively independent
set λ = logp q and M = dlogq ne−κdiscrepancy of sequence ({λm})M−1
m=0 is ≤ C1 M

discrepancy bounds largest gap in sequence{logp n} − C1 M −κ ≤ {λm} ≤ {logp n}≈Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Proof of Upper BoundApproximation by Power-products
there are positive constants C and κ with−κne −C (log n)αm≤ p1α1 . . . pm≤ntwo bases p and q multiplicatively independent
set λ = logp q and M = dlogq ne−κdiscrepancy of sequence ({λm})M−1
m=0 is ≤ C1 M

discrepancy bounds largest gap in sequence{logp n} − C1 M −κ ≤ {λm} ≤ {logp n}≈Multi-Base Representations

logp n − C1 M −κ ≤ ` + λm ≤ logp n−κne −C (log n)≤ p`qm ≤ nDaniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Proof of Upper BoundApproximation by Power-products
there are positive constants C and κ with−κne −C (log n)αm≤ p1α1 . . . pm≤ntwo bases p and q multiplicatively independent
set λ = logp q and M = dlogq ne−κdiscrepancy of sequence ({λm})M−1
m=0 is ≤ C1 M

discrepancy bounds largest gap in sequence{logp n} − C1 M −κ ≤ {λm} ≤ {logp n}≈Multi-Base Representations

logp n − C1 M −κ ≤ ` + λm ≤ logp n−κne −C (log n)≤ p`qm ≤ n⇒ upper bound follows
Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

History & Related Work

“Lower” Bound / Sharpness
infinitely many integers n whose minimal
Hamming weight is greater than
K2

log n
log log n · log log log nbases 2, 3 (Dimitrov–Howe 2011)
bases 2, 3, 5 (Yu–Wang–Li–Tian 2013)

Multi-Base Representations



Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

History & Related Work

“Lower” Bound / Sharpness
infinitely many integers n whose minimal
Hamming weight is greater than
K2

log n
log log n · log log log nbases 2, 3 (Dimitrov–Howe 2011)
bases 2, 3, 5 (Yu–Wang–Li–Tian 2013)

Multi-Base Representations



Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Proof of Sharpness: Counting Representations
number of different power-products
appearing in multi-base representations of {1, 2, . . . , N}
≤ T (N) :=

m
Y
j=1

Multi-Base Representationsm(cj log N) = (log N)

m
Y

cj

j=1

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Proof of Sharpness: Counting Representations
number of different power-products
appearing in multi-base representations of {1, 2, . . . , N}
≤ T (N) :=

m
Y
j=1

m

(cj log N) = (log N)

m
Y

cj

j=1

number of representations with weight at most K

K 
X
K
T (N)
RK (N) ≤(|D| − 1)k ≤ |D|T (N)kk=1

Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Proof of Sharpness: Counting Representations
number of different power-products
appearing in multi-base representations of {1, 2, . . . , N}
≤ T (N) :=

m
Y
j=1

m

(cj log N) = (log N)

m
Y

cj

j=1

number of representations with weight at most K

K 
X
K
T (N)
RK (N) ≤(|D| − 1)k ≤ |D|T (N)kk=1suppose all integers in 2s−1 + 1, 2s−1 + 2, . . . , 2s
have a representation with weight at most K , i.e.
K
|D|T (2s ) ≥ RK (2s ) ≥ 2s−1
take logarithms
Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Different Point of View: Communication Complexity
Communication Complexity
Set-up:
Alice and Bob both hold ` bits of information(nonnegative integers less than 2` )Bob wants to checkif both hold the same information

Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Different Point of View: Communication Complexity
Communication Complexity
Set-up:
Alice and Bob both hold ` bits of information(nonnegative integers less than 2` )Bob wants to checkif both hold the same information
Alice send some piece of information(according protocol)
Bob says“=”“6=”“more”

Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Different Point of View: Communication Complexity
Communication Complexity
Set-up:
Alice and Bob both hold ` bits of information(nonnegative integers less than 2` )Bob wants to checkif both hold the same information
Alice send some piece of information(according protocol)
Bob says“=”“6=”“more”

for each deterministic algorithm/protocol
instance where ` communication bits needed
Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Proof of Sharpness: Communication Complexity

assume n has multi-baserepresentation
log n with only o log log n summands
convert above ` = blog nc-bit instanceto multi-base representation
summand can be denoted by O(log log n) bits

Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Introduction

Around Multi-base Expansions

Upper Bound“Lower” Bound

Proof of Sharpness: Communication Complexity

assume n has multi-baserepresentation
log n with only o log log n summands
convert above ` = blog nc-bit instanceto multi-base representation
summand can be denoted by O(log log n) bits
Alice only needs
O(log log n) · o log n 
= o(log n)
log log nbits to tell Bob everything

Multi-Base Representations

Daniel Krenn, AAU Klagenfurt, Austria

Minimal Hamming Weight
Theorem (K–Suppakitpaisarn–Wagner 2018)
fix bases p1 , . . . , pm (m ≥ 2)
multiplicatively independent
fix digit set containing 1
there exist positive constants K1 and K2(U) each integers n has representation
with Hamming weightat most K1 logloglogn n(L) infinitely many positive integers nwith no representation
with Hamming weightless than K2 logloglogn nMulti-Base Representations,

Daniel Krenn, AAU Klagenfurt, Austria