On the discretised ABC sum-product problem
Full text
This is a sel -a chi ed e sion o an o iginal a icle. This e sion
may di e om he o iginal in pagina ion and ypog aphic de ails.
Au ho (s):
Ti le:
Yea :
Ve sion:
Copy igh :
Righ s:
Righ s u l:
Please ci e he o iginal e sion:
CC BY-NC 4.0
h ps://c ea i ecommons.o g/licenses/by-nc/4.0/
On he disc e ised ABC sum-p oduc p oblem
© 2023 he Au ho s
Accep ed e sion (Final d a )
O ponen, Tuomas
O ponen, T. (2024). On he disc e ised ABC sum-p oduc p oblem. T ansac ions o he Ame ican
Ma hema ical Socie y, Ea ly online. h ps://doi.o g/10.1090/ an/9094
2024
a Xi :2110.02779 3 [ma h.CO] 10 No 2023
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM
TUOMAS ORPONEN
ABSTRACT. Le 0ăβďαă1and κą0. I p o e ha he e exis s ηą0such ha he
ollowing holds o e e y pai o Bo el se s A, B ĂRwi h dimHA“αand dimHB“β:
dimH cPR: dimHpA`cBq ď α`ηu ď α´β
1´β`κ.
This ex ends a esul o Bou gain om 2010, which con ained he case α“β. The pape
also con ains a δ-disc e ised, and somewha s onge , e sion o he es ima e abo e, and
new in o ma ion on he size o long sums o he o m a1B`...`anB.
CONTENTS
1. In oduc ion 2
1.1. Rela ed wo k 4
1.2. Compa ison o classical p ojec ion heo ems 7
1.3. Pape ou line and p oo ske ch 7
1.4. Acknowledgemen s 9
2. No a ion and p elimina ies 9
2.1. Dyadic cubes and co e ing numbe s 9
2.2. En opy 9
3. Th ee ini ial educ ions 11
3.1. Reduc ion o he case whe e Bhas small doubling 11
3.2. Reducing he F os man cons an o ν14
3.3. Remo ing e e ence o subse s 17
3.4. Bonus educ ion 20
4. P oo o Theo em 3.28 21
4.1. P elimina ies 21
4.2. Shme kin’s in e se heo em 21
4.3. Applying he in e se heo em 23
4.4. P uning B1 o imp o e sepa a ion I 25
4.5. In e als wi h small bu non-ze o B1-b anching 26
4.6. B anching o A1on ypical in e als in N`29
4.7. P uning B1 o imp o e sepa a ion II 30
4.8. Elemen a y p ojec ion es ima es 32
4.9. P ojec ing pieces o A1ˆB234
4.10. Final mul iscale a gumen 36
Da e: No embe 13, 2023.
2010 Ma hema ics Subjec Classi ica ion. 11B30 (p ima y) 28A80 (seconda y).
Key wo ds and ph ases. Disc e ised sum-p oduc p oblem, P ojec ions, Hausdo dimension.
T.O. is suppo ed by he Academy o Finland ia he p ojec s Quan i a i e ec i iabili y in Euclidean and
non-Euclidean spaces and Incidences on F ac als, g an Nos. 309365, 314172, 321896.
1
2 TUOMAS ORPONEN
5. Hausdo dimension es ima es 38
5.1. Reducing Theo em 1.6 o Theo em 1.8: ou line 38
5.2. A oy e sion 39
5.3. Reduc ion o a weake oy heo em 39
5.4. P oo o he weake oy heo em 41
5.5. P oo o he main heo em 47
5.6. P oo o Co olla y 1.7 51
Re e ences 54
1. INTRODUCTION
Le A, B, C ĂRbe la ge bu ini e se s. Is i ue ha he e exis s some cPCsuch ha
|A`cB| " |A|? He e |¨| e e s o ca dinali y. No necessa ily: conside o example
An“!1
n1{2,2
n1{2,...,1)and Bn“!1
n1{4,2
n1{4,...,1)“Cn.(1.1)
I is no ha d o check ha o e e y ǫą0, he e exis s nPNsuch ha |An`BnCn| ď
nǫ|A|, so in pa icula |An`cBn| ď nǫ|A| o all cPCn. The p oblem can be ixed by
adding one assump ion: |B||C| " |A|. Then, a posi i e answe o he ques ion ollows
easily om he Szeme édi-T o e heo em [39] applied o he plana se AˆB. The
equi emen |B||C| " |A|is also necessa y, as one can see by a ian s o (1.1).
The ABC sum-p oduc p oblem, s a ed abo e, also makes sense in con ex s whe e
he Szeme édi-T o e bound is no a ailable, o example i A, B, C ĂZp, and pPN
is p ime. Again, i u ns ou ha he lowe bound |B||C| " |A|yields he exis ence o
cPCwi h |A`cB| " |A|. One way o show his is o adap elemen a y echniques o
Ga ae [11], Glibichuk and Konyagin [12], and Bou gain [4]. The de ails can be ound in
[29]. Ano he way is o apply di ec ly an incidence bound in ini e ields due o S e ens
and de Zeeuw [38]. The heo em o S e ens and de Zeeuw gi es a s onge lowe bound
o |A`cB| han he elemen a y app oach (see [29, P oposi ion 1.3] o he de ails), bu
ul ima ely elies on he polynomial me hod.
The pu pose o his pape is o conside he δ-disc e ised ABC sum-p oduc p oblem in
R, and lowe bounds o dimHpA`cBq, he Hausdo dimension o A`cB. The δ-
disc e ised p oblem is o he wise he same as he ques ion we s a ed wi h, bu ins ead
o coun ing he ca dinali y |A`cB|, we seek lowe bounds o he δ-co e ing numbe
|A`cB|δ o some small scale δą0. We will also assume ha he se s A, B, C a e δ-
sepa a ed, and ha e ca dinali ies |A| “ δ´α,|B| “ δ´β, and |C| “ δ´γ. In his a ian o
he p oblem, hypo heses on |B||C|need o be coupled wi h addi ional non-concen a ion
condi ions o hope o posi i e esul s. The ollowing heo em o Bou gain [5] om 2010
(ex ending his own wo k [2] om 2003) ea s he case A“B:
Theo em 1.2 (Bou gain).Gi en αP p0,1qand γ, κ ą0, he e exis ǫ0, ǫ ą0such ha ha he
ollowing holds o δą0su icien ly small.
Le νbe a p obabili y measu e on 0,1ssa is ying νpBpx, qq ď γ o all xPRand 0ă
ďδǫ0. Le addi ionally AĂ 0,1sbe a δ-sepa a ed se wi h |A| ě δ´α, which also sa is ies he
non-concen a ion condi ion |AXBpx, q| ď κ|A| o xPRand δď ďδǫ0.
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 3
Then, he e exis s a poin cPsp pνqsuch ha
|A`cA|δěδ´α´ǫ.(1.3)
Rema k 1.4.Bou gain’s heo em admi s he ollowing s onge e sion, which, o he bes
o my knowledge, was i s s a ed and p o ed by He [17, Theo em 1] (see also [5, (7.43),
p. 221] o a sligh ly weake esul ): unde he assump ions o Theo em 1.2, he e exis s
a poin cPsp pνqsuch ha |πcpGq|δěδ´α´ǫ o all subse s GĂAˆAo ca dinali y
|G| ě δǫ|A|2. He e πcpx, yq “ x`cy. This e sion is use ul o p o ing lowe bounds
o dimHpA`cAq. Bou gain also p o ed such lowe bounds in [5, Theo em 4] wi hou
explici ly men ioning he s onge e sion o Theo em 1.2: while his p oo is co ec ,
i equi es some ca e om he eade o ex ac all he de ails. Applying he s onge
e sion di ec ly is simple , see [17, Theo em 2].
To see he connec ion be ween Theo em 1.2 and he ABC p oblem, le CĂ 0,1sbe
aδ-sepa a ed se sa is ying |CXBpx, q| ď γ|C| o all xPRand δď ďδǫ0. Then
he uni o mly dis ibu ed p obabili y measu e νon he δ-neighbou hood o Csa is ies
νpBpx, qq . γ, and i ollows om (1.3) ha he e exis s cPCwi h |A`cA|δěδ´α´ǫ.
Theo em 1.2 o mally only ea s he case A“B, bu an inspec ion o i s p oo (o ,
mo e di ec ly, an applica ion o [5, Theo em 3]), e eals ha he esul emains alid o
wo di e en δ-sepa a ed se s A, B Ă 0,1s, p o ided ha |A| “ |B|, o a leas |B| « |A|.
The p ecise meaning o "«" is de ined ia he a ious cons an s appea ing in [5, Theo em
3]. To he bes o my knowledge, Theo em 1.2 does no co e he case whe e |A| “ δ´α
and |B| “ δ´βwi h βăα( he case βąαis no ele an he e: hen |A`cB|δ&|B| " |A|
o any cPRwi h |c| „ 1).
The ollowing conjec u e would co espond o he assump ion |B||C| " |A|which
su ices in he disc e e a ian s (on Rand Zp) o he ABC sum-p oduc p oblem:
Conjec u e 1.5. Le α, β, γ P p0,1qwi h βďαand γąα´β. Assume ha A, B, C Ă 0,1s
a e δ-sepa a ed se s wi h ca dinali ies |A| ď δ´α,|B| “ δ´β, and |C| “ δ´γ. Assume mo eo e
ha |BXBpx, q| . β|B|and |CXBpx, q| . γ|C| o all xPRand ą0. Then, he e
exis s ǫ“ǫpα, β, γq ą 0and a poin cPCsuch ha |A`cB|δ&α,β,γ δ´ǫ|A|.
The lowe bound o γin Conjec u e 1.5 is necessa y, bu he non-concen a ion as-
sump ions on Band Ca e qui e likely no sha p. The main esul o his pape is he ol-
lowing pa ial esul , whe e he lowe bound γąα´βis upg aded o γą pα´βq{p1´βq:
Theo em 1.6. Le 0ăβďαă1and κą0. Then, o e e y γP ppα´βq{p1´βq,1s, he e
exis ǫ0, ǫ, δ0P p0,1
2s, depending only on α, β, γ, κ, such ha he ollowing holds. Le δP2´N
wi h δP p0, δ0s, and le A, B Ă pδ¨ZqX 0,1ssa is y he ollowing hypo heses:
(A) |A| ď δ´α.
(B) |B| ě δ´β, and Bsa is ies he ollowing F os man condi ion:
|BXBpx, q| ď κ|B|, δ ď ďδǫ0.
Fu he , le νbe a Bo el p obabili y measu e wi h sp pνq Ă 1
2,1s, and sa is ying he F os man
condi ion νpBpx, qq ď γ o xPRand 0ă ďδǫ0. Then, he e exis s a poin cPsp pνqsuch
ha he ollowing holds: i GĂAˆBis any subse wi h |G| ě δǫ|A||B|, hen
|πcpGq|δěδ´ǫ|A|,whe e πcpx, yq “ x`cy.
4 TUOMAS ORPONEN
Theo em 1.6 wi h α“β eco e s Theo em 1.2, and he s onge e sion in Rema k 1.4.
In ac , Theo em 1.6 is o mally s onge han Theo em 1.2, since Theo em 1.6 does no
impose any non-concen a ion condi ions on A. This is use ul in p o ing Co olla y 1.11
below. Theo em 1.6 easily yields he ollowing co olla y o Hausdo dimension:
Co olla y 1.7. Le 0ăβďαă1and κą0. Then, he e exis s η“ηpα, β, κq ą 0such ha
i A, B ĂRa e Bo el se s wi h dimHA“α,dimHB“β, hen
dimH cPR: dimHpA`cBq ď α`ηu ď α´β
1´β`κ.
The case α“βis al eady con ained in Bou gain’s pape [5]. The educ ion om
Theo em 1.6 o Theo em 1.7 is a s anda d pigeonholing a gumen , and goes he same
way as he p oo o [17, Theo em 2]. Fo comple eness, I gi e he de ails in Sec ion 5.6. A
"con inuous" e sion o Conjec u e 1.5 would imply ha he numbe pα´βq{p1´βqin
Co olla y 1.7 can be eplaced by α´β.
The lowe bound on |πcpGq|δin Theo em 1.6 is indispensable o deducing Co olla y
1.7, bu makes Theo em 1.6 di icul o p o e wi h a di ec assaul . Ins ead, Theo em 1.6
will be o mally educed o he ollowing simple e sion, which only ea s G“AˆB:
Theo em 1.8. Le 0ăβďαă1and κą0. Then, o e e y γP ppα´βq{p1´βq,1s, he e
exis ǫ, ǫ0, δ0P p0,1
2s, depending only on α, β, γ, κ, such ha he ollowing holds. Le δP2´N
wi h δP p0, δ0s, and le A, B Ă pδ¨ZqX 0,1ssa is y he ollowing hypo heses:
(A) |A| ď δ´α.
(B) |B| ě δ´β, and Bsa is ies he ollowing F os man condi ion:
|BXBpx, q| ď κ|B|, δ ď ďδǫ0.
Fu he , le νbe a Bo el p obabili y measu e wi h sp pνq Ă 0,1s, sa is ying he F os man condi-
ion νpBpx, qq ď γ o xPRand δď ďδǫ0. Then, he e exis s cPsp pνqsuch ha
|A`cB|δěδ´ǫ|A|.
Theo em 1.8 is he hea o he pape , bu as a as I know, i is also news ha Theo em
1.6 can be li e ally educed o Theo em 1.8. This akes some wo k, bu is mos ly a ma e
o "s anda d echniques" in addi i e combina o ics. Since hese de ails can be ca ied ou
wi hou e e ence o he es o he pape , hey a e pos poned o Sec ion 5.1.
Rema k 1.9.As w i en abo e, Theo em 1.6 is deduced om Theo em 1.8 in Sec ion 5.1. A
a ian o his p oblem is he ollowing. Assume ha we wan o p o e Theo em 1.6 wi h
a ixed non-concen a ion exponen "κ". Can we deduce i om he e sion o Theo em
1.8 wi h he same κ? The answe is "almos ": i u ns ou ha in o de o deduce Theo em
1.6 o a ixed non-concen a ion exponen κą0, we only need o in oke Theo em 1.6
wi h non-concen a ion exponen ¯κP p0, κqa bi a ily close o κ: howe e , he alues o
he cons an s ǫ, δ0p oduced by he a gumen will end o 0as ¯κÕκ. The educ ions
in Sec ion 5.1 will be w i en in such a way ha his claim becomes appa en – and he
ma e will be u he e eshed in Rema ks 5.11,5.37, and 5.57.
1.1. Rela ed wo k. A ele an piece o ecen li e a u e is he pape o Gu h, Ka z, and
Zahl [13], whe e he au ho s ex end an a gumen (due o Ga ae [11]) om ini e ields
o gi e a new, ela i ely simple, p oo o Bou gain’s Theo em 1.2. Gi en ha he Zp
analogue o Conjec u e 1.5 is known [29], i may be plausible ha Conjec u e 1.5 can be
sol ed by ex ending he Zpa gumen in he ashion o Gu h, Ka z, and Zahl. I was no
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 5
able o ca y his ou , and he e is why. The p oo in [29] is chie ly based on he ollowing
lemma: i A, B ĂZpa e se s wi h |A| “ pαand |B| “ pβ, hen o e e y ηą0 he e exis s
an in ege n“npα, β, ηq P N, and choices a1,...,anP ˘Asuch ha
|a1B`...`anB|&p´ηmin |A||B|, pu.(1.10)
I was no able o ex end he ini e ield echniques in [29] o (di ec ly) p o e a δ-disc e ised
analogue o (1.10). Howe e , once Theo em 1.8 is known, i can be applied o make
pa ial p og ess owa ds a δ-disc e ised analogue o (1.10) (a sha pe esul would ollow
om Conjec u e 1.5 in he same way):
Co olla y 1.11. Le β, γ P p0,1qand 0ăηăγp1´βq. Then, he e exis s ǫ0, δ0ą0and nPN,
depending on β, γ, η, such ha he ollowing holds o all δP p0, δ0s. Le B, C Ă pδ¨ZqX 0,1s
be non-emp y se s sa is ying
|BXBpx, q| ď β|B|and |CXBpx, q| ď γ|C|(1.12)
o xPRand δď ďδǫ0. Then, he e exis poin s c1,...,cnPCsuch ha
|c1B`...`cnB|δěδ´γ´βp1´γq`η“δ´β´γp1´βq`η.
Rema k 1.13.A classical p ojec ion heo em o Kau man [20] implies he exis ence o cPC
such ha |B`cB|δ'max δ´β, δ´γu. Fo γąβ, a ecen sha pening o Kau man’s
heo em by he au ho and Shme kin [28] e en yields |B`cB|δěδ´γ´η o some η“
ηpβ, γq ą 0, and o δą0small enough ( o be clea , his s a emen is only a co olla y
o he main esul in [28]). In compa ison, Co olla y 1.11 gi es a a mo e subs an ial
imp o emen , bu a he cos o adding he numbe o summands. I gi e he simple
p oo s aigh away.
P oo o Co olla y 1.11.S a by applying Theo em 1.8 wi h
α:“β`γp1´βq´ηP pβ, 1q, β, κ :“β, and γ.
No e ha γą pα´βq{p1´βq, so he pa ame e s a e admissible. Le ǫ, ǫ0, δ0P p0,1
2sbe he
cons an s gi en by Theo em 1.8 wi h α, β, γ, κ. Le ν:“ |C|´1¨H0|Cbe he no malised
coun ing measu e on C, which sa is ies he F os man condi ion νpBpx, qq ď γ o all
xPRand δď ďδǫ0by (1.12). We also no e ha |B| ě δ´βby (1.12) applied wi h “δ,
and Bsa is ies he κ“β-dimensional F os man condi ion equi ed in Theo em 1.8.
We cons uc a sequence o se s HnĂδ¨Z,nPN, wi h he ollowing g eedy algo i hm.
We i s de ine H1:“ pc1Bqδa bi a ily, whe e Aδ:“ pδ¨ZqXApδq. Then, we assume ha
Hnhas al eady been de ined o some ně1, and we le
Hn`1:“Hn`pcn`1BqδĂδ¨Z,
whe e cn`1PCmaximises |Hn`cB|δamong all choices cPC. We obse e (by induc ion)
ha HnĂ pδ¨ZqX 0, ns, so |Hn| ď nδ´1. Fo a bi a y NPNwi h Ně2, i ollows om
he pigeonhole p inciple ha he e exis s nP 1,...,N ´1usuch ha
|Hn`1| ď 2pNδ´1q1{pN´1q|Hn| ď 4δ´1{pN´1q|Hn|.(1.14)
Indeed, i he i s inequali y ailed o e e y nP 1,...,N ´1u, hen
|HN| ą 2pNδ´1q1{pN´1q|HN´1| ą ...ą2N´1pNδ´1qpN´1q{pN´1q|H1| ě 2N´1Nδ´1,
6 TUOMAS ORPONEN
con adic ing ha HNĂ pδ¨ZqX 0, Ns. By de ini ion o Hn`1, (1.14) implies
|Hn`cB|δ.|Hn`1| ď 4δ´1{pN´1q|Hn|, c PC. (1.15)
We now choose NPNso la ge ha 4δ´1{pN´1qďδ´ǫ{2, whe e ǫ“ǫpα, β, γq ą 0was
one o he cons an s p oduced by Theo em 1.8. Since Band νsa is y he hypo heses o
Theo em 1.8, we see om (1.15) ha A:“Hnmus ail he hypo heses. Howe e , he
only hypo heses on Ain Theo em 1.8 a e
AĂ pδ¨ZqX 0,1sand |A| ď δ´α.
O cou se HnĆ 0,1s, bu his is no eally ele an : we may ind kP 0,...,n´1usuch
ha |HnX k, k `1s| ě 1
N|Hn|. Now, de ining ins ead A:“ pHnX k, k `1sq ´ ku, we
ha e AĂ pδ¨ZqX 0,1s, and |A`cB|δďδ´ǫ{2|Hn| ď δ´ǫ|A|by (1.15), o δą0so small
ha δ´ǫ{2ěN. This iola es Theo em 1.8, unless
|Hn| ě |A| ą δ´α“δ´β´γp1´βq`η,
and his is wha he co olla y claimed.
The ABC sum-p oduc p oblem is, o cou se, ela ed o he highly ac i e a ea o sum-
p oduc heo y. The main open ques ion is he E d˝os-Szeme édi sum-p oduc conjec u e
[8]: i AĂRo AĂZpis a ini e se (pPNis p ime), he E-S conjec u e asks o p o e
ha
max |A`A|,|A¨A|u &ǫ|A|2´ǫ, ǫ ą0.
The esea ch a ound his p oblem is oo ac i e o su ey he e: I only men ion he pape s
[32] o Rudne -S e ens and [24] o Mohammadi-S e ens o some cu en wo ld eco ds,
and u he e e ences. Fo esul s on he he δ-disc e ised a ian o he E d˝os-Szeme édi
p oblem, see [13] by Gu h-Ka z-Zahl, and [7] by D ˛ab owski, he au ho , and Villa.
Bou gain’s δ-disc e ised sum-p oduc es ima e, Theo em 1.2, has been ex ended in
a ious ways beyond he eal line. Fo example, He [17] ound a e sion o he he-
o em in Rn. Closely ela ed a e also he wo ks [3,6] by Bou gain-Gambu d, [16] by
He, [18] by He-de Saxcé, [1] by Benois -de Saxcé, and [21] by Li. These pape s con-
ain δ-disc e ised sum-p oduc o p oduc heo ems in a ious Lie g oups. Viewing he
δ-disc e ised ABC sum-p oduc p oblem as a special case o a δ-disc e ised incidence
p oblem be ween poin s and δ- ubes in R2, he pape s [10,14] a e also ele an .
Theo ems 1.2 and 1.8 can be iewed as s a emen s conce ning linea p ojec ions o
plana se s, as discussed mo e in he nex subsec ion. S a ing wi h his in e p e a ion,
one may ask i analogous s a emen s hold o non-linea p ojec ions. Examples o pa -
icula in e es a e he pinned dis ance p ojec ions △xpyq “ |x´y|and he adial p ojec ions
πxpyq “ px´yq{|x´y|. Again, he li e a u e is oo b oad o a su ey, bu see he e-
cen pape s [36] by Shme kin, [37] by Shme kin-Wang, and [31] by Raz-Zahl o ecen
exci ing de elopmen s and mo e e e ences.
Finally, Conjec u e 1.5 was ecen ly sol ed by he au ho [27] o Ahl o s- egula se s
A, B Ă 0,1s. In ac , a much s onge esul can be ob ained o such se s. Le α, β P
p0,1q. Assume ha A, B ĂRa e closed se s, Ais α-Ahl o s- egula and Bis β-Ahl o s-
egula . Then
dimH cPR: dimpA`cBq ă α`ηu “ 0
o η:“βp1´αq{p2´αq ą 0. (The pape [27] also con ains a δ-disc e ised e sion.)
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 7
1.2. Compa ison o classical p ojec ion heo ems. A popula opic in ac al geome y
is o s udy he o hogonal p ojec ions o subse s o Rd. In his sec ion we will see wha
"classical" p ojec ion heo ems in ac al geome y ha e o say abou he size o A`cB.
Fo ePS1, le πe:R2Ñspanpeqbe he o hogonal p ojec ion. A heo em o Kau man
[20] om 1968, sha pening a seminal esul o Ma s and [22], s a es he ollowing: i
KĂR2is a compac se wi h dimension dimHK“ , hen
ΣpK, sq:“dimH ePS1: dimHπepKq ď su ď s, 0ďsă . (1.16)
Ano he classical es ima e, due Pe es-Schlag [30] bu building on a Fou ie -analy ic ech-
nique in oduced by Falcone [9], shows ha
ΣpK, sq ď max 1`s´ , 0u,0ďsď . (1.17)
A olklo e conjec u e (made explici in [25]) p oposes o imp o e (1.16)-(1.17) o ΣpK, sq ď
max 2s´ , 0u o 0ďsă . Bou gain [5] showed ha ΣpK, sq Ñ 0as sÑ {2, which
suppo s he conjec u e. A ecen p ep in [28] o he au ho and Shme kin addi ionally
shows ha ΣpK, sq ď s´ǫ o some ǫ“ǫps, q ą 0, o all 0ďsă .
The connec ion be ween o hogonal p ojec ions and he A`cB p oblem is he ollow-
ing. Take K“AˆB, whe e A, B ĂR. Then, o ePS1z p0,1q,p0,´1qu, he p ojec ion
πepKqcan, up o escaling, be ew i en as A`cB, o a sui able c“cpeq P R. Wi h his
in mind, he bounds (1.16)-(1.17) can be used o deduce he ollowing.
Le 0ăβďαă1. Assume ha A, B ĂRa e Bo el se s wi h dimHA“αand
dimHB“β. Then, (1.16)-(1.17) applied wi h :“dimHpAˆBq ě α`βyield
dimH cPR: dimHpA`cBq ď αu ď min α, 1´βu.
In con as , le ing ηÑ0in Co olla y 1.7 gi es he uppe bound pα´βq{p1´βq. This
bound is ăα o all αă1, and also ă1´βwhene e 0ăβďαă3
4. I αą3
4, hen he
"1´β" es ima e coming om (1.17) is be e o some alues o β, e.g. β“1
2.
The conjec u ed bound ΣpK, sq ď max 2s´ , 0uwould imply he (Hausdo dimen-
sion e sion o ) Conjec u e 1.5:
dimH cPR: dimHpA`cBq ď αu “ ΣpAˆB, αq ď max 2α´ , 0u ď α´β.
To summa ise, Co olla y 1.7 is s onge han all p e ious esul s in he case K“AˆB
and s“α“dimHAă3
4, whe eas he conjec u e ΣpK, sq ď max 2s´ , 0uis e en
s onge han ( he Hausdo dimension e sion o ) Conjec u e 1.5.
1.3. Pape ou line and p oo ske ch. The p oo o Theo em 1.6 has wo dis inc compo-
nen s: he i s one is a educ ion o Theo em 3.28, which di e s om Theo em 1.6 in he
ollowing aspec s: (a) νsa is ies a F os man condi ion on all scales δď ď1, (b) he se
Bhas small doubling, ha is |B`B| ď δ´ǫ|B|, and (c) he conclusion |πcpGq|δěδ´ǫ|A|
is only equi ed o G“AˆB. These educ ions a e pe o med in se e al s eps:
Theo em 3.28 §3.3
ùñ Theo em 3.15 §3.2
ùñ Theo em 3.1
§3.1
ùñ Theo em 1.8 §5.4
ùñ Theo em 5.4
§5.3
ùñ Theo em 5.3 §5.5
ùñ Theo em 1.6.
8 TUOMAS ORPONEN
The ou line o he pape is ha he educ ion om Theo em 1.8 o Theo em 3.28 is pe -
o med i s , hen Theo em 3.28 is p o ed wi h a di ec a gumen , and inally Theo em
1.6 is educed o Theo em 1.8 in Sec ion 5.1.
The addi ional assump ions (a)-(c) in Theo em 3.28 a e echnically impo an . How-
e e , a he cu en le el o discussion, all he heo ems abo e a e indis inguishable. So,
o example, he eade may hink ha he ollowing ou line conce ns he p oo o Theo-
em 1.8, which has he simples s a emen .
Fo he sake o exposi ion, I make he ollowing addi ional assump ions on Aand B.
Bo h se s ha e a " ee" (o "Can o se ") s uc u e: o a sui able pa ame e mPN, each
dyadic in e al IPDms in e sec ing Acon ains exac ly RApsqsub-in e als in Dmps`1q
which in e sec A. The same is assumed o B. The numbe s RApsqand RBpsqa e known
as he b anching numbe s o Aand B, espec i ely. Assume ha he scale pa ame e δą0
has he special o m δ“2´mN o some NPN( hus RApsq “ 1“RBpsq o sěN, since
A, B we e assumed o be δ-sepa a ed). We make e en mo e assump ions:
(P1) Fo e e y sPN, ei he RBpsq “ 1o RApsq “ 2m.
(P2) |B| “ δ´β, and o e e y sPN, ei he RBpsq “ 1o RBpsq “ 2m.
P ope y (P2) needs he small doubling assump ion |B`B| ď δ´ǫ|B|. Now, as we will see
in a momen , he key ques ion u ns ou o be: gi en a scale sPNwi h RBpsq “ 1, wha
uppe bound can we gua an ee o RApsq? I u ns ou ha we can easily use (P1)-(P2) o
deduce an answe .
Assume ha RApsq ě 2Γm o all sP 0,...,N ´1u “: Nswi h RBpsq “ 1. W i e
N:“ sP Ns:RBpsq “ 1u, and no e ha RApsq “ 2m o all sP NszNby assump ion
(P1). Now, we may calcula e a lowe bound on he ca dinali y o Aas ollows:
2αmN ě |A| “ ź
sP Ns
RApsq “ ź
sP Ns z N
RApsq¨ ź
sPN
RApsq ě 2mpN´|N|q ¨2Γm|N|.(1.18)
On he o he hand, by assump ion (P2), we ha e
2βmN “ |B| “ ź
sP Ns z N
2m“2mpN´|N|q,(1.19)
so may sol e N´|N| “ βN and |N| “ p1´βqN. Plugging his in o ma ion in o (1.18)
yields Γď pα´βq{p1´βq. This is whe e he nume ology in Theo em 1.8 comes om.
Namely, he a gumen abo e shows ha i Γą pα´βq{p1´βq, hen he e exis s a leas
one scale sP Nssuch ha RApsq ď 2Γm. In ac , he same mus be ue o a posi i e
ac ion o he scales, say GĂ Ns, whe e |G|{Nonly depends on Γ´pα´βq{p1´βq.
A e his obse a ion, we ocus a en ion sepa a ely on pieces o AˆBo he o m
pAXIqˆpBXJq, whe e I, J PDms a e in e als in e sec ing A, B, espec i ely, and sPG.
By de ini ion, |AXI|mps`1q“RApsq ď 2Γm o some Γsligh ly la ge han pα´βq{p1´βq.
To be p ecise, we choose pα´βq{p1´βq ă Γăγ, whe e γis he F os man exponen o he
measu e νin Theo em 1.8. I we addi ionally knew ha |BXJ|2´mps`1q“RBpsq ě 2ǫm
o some ǫą0, and he poin s in BXJa e well enough sepa a ed, we could a his
poin use an elemen a y a gumen (essen ially he "po en ial heo e ic me hod" due o
Kau man [20]) o deduce ha
|pAXIq`cpBXJq|2´mps`1qě2ǫm|AXI|2´mps`1q(1.20)
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 15
Wi h hese choices o cons an s, ix δP p0, δ0s, and le A, B Ă pδ¨ZqX 0,1sbe se s, and
le νbe a Bo el p obabili y measu e on 0,1s, sa is ying he hypo heses in Theo em 3.1.
To land in a si ua ion whe e Theo em 3.15 becomes applicable, we conside ini ially he
measu e ¯ν:“ν˚p´νq, whe e ´νpAq:“νp´Aq. E iden ly sp p¯νq Ă ´1,1s. As Bou gain
shows in [5, (5.5)], he measu e ¯νhas he p ope y
¯νpBpx, qq ď 4¨¯νpBp0, qq ď 4¨sup
yPR
νpBpy, qq, x PR, ą0.(3.20)
Now, le c0ě0be he in imum o he numbe s such ha
¯νpBp0, c0qq ą 5¨cγ
0,(3.21)
i any such numbe s exis . E iden ly c0P 0,1s, since ¯νis a p obabili y measu e on
Bp0,1q. I no c0as in (3.21) exis s, hen le c0:“max |c|:cPsp p¯νqu, and no e ha
5¨cγ
0ě¯νpBp0, c0qq ě ¯νpBp0,1qq “ 1ùñ c0ě5´1{γěδǫ0,(3.22)
assuming he e ha δ0ěδis su icien ly small in e ms o γ, ǫ0. Assume hen ha c0, as
in (3.21), exis s. Since supyPRνpBpy, qq ď γ o all 0ă ďδǫ0by assump ion, (3.20)
implies ha c0ěδǫ0. In bo h cases, c0ěδǫ0. Mo eo e , we no e ha sp pνqX c0,´c0u ‰
Hin bo h cases (in he non- i ial case, o he wise some smalle alue o c0would also
sa is y (3.21)).
We hen conside he e-no malised measu e ¯νc0de ined by
¯νc0pHq:“1
¯νpBp0,c0qq ¨¯ν|Bp0,c0qpc0¨Hq, H ĂR,
which sa is ies sp p¯νc0q “ c´1
0¨psp ¯νX¯
Bp0, c0qq Ă ´1,1s. Clea ly ¯νc0is a Bo el p obabili y
measu e. Mo eo e , i xPRand P δ, 1s, hen, assuming ha c0P 0,1swas de ined ia
(3.21), we ha e
¯νc0pBpx, qq ď ¯νpBpc0x, c0 qq
¯νpBp0, c0qq
(3.20)
ď4¨¯νpBp0, c0 qq
5¨cγ
0ď4¨5¨pc0 qγ
5¨cγ
0“4¨ γ.
I c0was, ins ead, de ined as c0“max |c|:cPsp p¯νqu, hen ¯νpBp0, c0qq “ 1, so
¯νc0pBpx, qq ď ¯νpBpc0x, c0 qq
¯νpBp0, c0qq
(3.20)
ď4¨¯νpBp0, c0 qq ď 20 ¨pc0 qγď20 ¨ γ.
The same es ima es a e also ue o ą1, since }¯νc0} “ 1. The e o e, in any case ¯νc0
sa is ies he hypo heses o Theo em 3.15 wi h F os man cons an 20.
We will no apply Theo em 3.15 di ec ly o he se s A, B, bu a he o A, pc0Bqδ, whe e
pc0Bqδ“ pδ¨ZqXpc0Bqpδq Ă pδ¨ZqX 0,1s.
E iden ly |pc0Bqδ|&c0|B| ě δǫ0|B|by (3.22). I ollows ha
|pc0Bqδ`pc0Bqδ|.|B`B| ď δ´ǫB|B|.δ´ǫ0´ǫB|pc0Bqδ|.
Since ǫ0`ǫBď¯ǫB{2by (3.18), and i δą0is su icien ly small, we conclude ha pc0Bqδ
sa is ies he small doubling assump ion in Theo em 3.15 wi h cons an ¯ǫB. We mo eo e
claim ha pc0Bqδsa is ies he F os man condi ion |pc0BqδXBpx, q| ď κ{2|pc0Bqδ| o all
16 TUOMAS ORPONEN
δď ďδ¯ǫ0. To see his, ix δď ďδ¯ǫ0ďδ2ǫ0ďc0δǫ0(by (3.18) and (3.22)), and no e ha
|pc0BqδXBpx, q| .|BXBpx, c´1
0 q|
ď pc´1
0 qκ¨|B|
.c´2
0¨ κ¨|pc0Bqδ|
ďδ´2ǫ0¨ κ{2¨ κ{2¨|pc0Bqδ|
(3.18)
ďδ2ǫ0¨ κ{2¨|pc0Bqδ|.
This implies |pc0BqδXBpx, q| ď κ{2|pc0Bqδ|, p o ided ha δ0ěδis su icien ly small.
We ha e now shown ha Theo em 3.15 is applicable wi h he pa ame e s α, β, γ, κ{2 o
he he se s A, pc0Bqδ, and he measu e ¯νc0.
Since δďδ0ď¯
δ0, Theo em 3.15 implies he exis ence o a poin cPsp p¯νc0q Ă ´1,1sX
c´1
0¨psp pνq´sp pνqqsuch ha
|A1`cpc0Bqδ| ě δ´¯ǫ|A|(3.23)
o all subse s A1ĂAwi h |A1| ě p1´¯ρq|A|. No e ha he poin cPsp p¯νc0qin (3.23) can
be w i en as c“c´1
0¨pc1´c2q o ce ain poin s c1, c2Psp pνq. The e o e
|A1`pc1´c2qB|δ“ |A1`c1´c2
c0¨c0B|δ&|A1`cpc0Bqδ|δěδ´¯ǫ|A|(3.24)
o all A1ĂAwi h |A1| ě p1´¯ρq|A|. We now claim ha he e exis s ¯cP c1, c2usuch ha
|A1`¯cB|δěδ´ǫ|A|, A1ĂA, |A1| ě p1´ρq|A|,(3.25)
assuming ha δ0ěδis small enough, depending on ǫ, ρ. This will p o e Theo em 3.1.
Assume ha (3.25) ails o bo h ¯cP c1, c2u, and le A1
1, A1
2ĂAbe subse s o ca dinal-
i ies |A1
j| ě p1´ρq,jP 1,2u, such ha
|A1
1`c1B| ă δ´ǫ|A|and |A1
2`c2B| ă δ´ǫ|A|.(3.26)
We i s obse e om he second inequali y in (3.26) ha
|A1
2`c2B|δďδ´ǫ|A| ď 2δ´ǫ|A1
2|.
By Lemma 3.16, o Ně1 he e exis s a subse A2
2ĂA1
2o ca dinali y |A2
2| ě p1´ρq|A1
2|
such ha
|A2
2´c2B|δ.ρ,N pδ´ǫq2N|A1
2|1`1{N.δ´ǫ¨2N`2´1{N|A2
2|.(3.27)
We apply his wi h N„log2p1{ǫqsa is ying ǫ¨2N`2„?ǫ. Since wi h his choice ǫ¨2N`2„
?ǫ!1{log2p1{ǫq „ 1{N, we ha e ǫ¨2N`1`1{Nď2{N„1{log2p1{ǫq, and we deduce
om (3.27) ha
|A2
2´c2B|δ.ǫ,ρ δ´C0{log2p1{ǫq|A2
2|
o some absolu e cons an C0ą0.
Now, ecall ha |A1
1| ě p1´ρq|A|and |A2
2| ě p1´ρq|A1
2| ě p1´?ρq|A|. Consequen ly,
he in e sec ion A1:“A1
1XA2
2sa is ies |A1| ě p1´ρ´?ρq|A|. E iden ly,
|A1`c1B| ď δ´ǫ|A|.δ´C0{log2p1{ǫq|A1|and |A1´c2B|.ρ,ǫ δ´C0{log2p1{ǫq|A1|.
By Lemma 3.3, he e exis s a u he subse A2ĂA1wi h
|A2| ě p1´ρq|A1| ě p1´ρqp1´ρ´?ρq|A|(3.19)
ě p1´¯ρq|A|
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 17
such ha
|A2`c1B´c2B|δ.ǫ,ρ δ´2C0{log2p1{ǫq|A2|(3.17)
ďδ´¯ǫ{2|A|.
This con adic s (3.24) o δą0small enough, depending on ǫ, ρ, and p o es (3.25). The
p oo o Theo em 3.1 is comple e.
3.3. Remo ing e e ence o subse s. In he p e ious educ ions, we ha e upg aded he
assump ions o Theo em 1.8 in wo ways: we ha e a anged he se B o ha e small
doubling, and he F os man cons an o ν o be 20. Howe e , he e has been a p ice:
whe eas Theo em 1.8 only claims ha |A`cB|δěδ´ǫ|A| o some cPsp pνq, Theo em
3.15 claims he exis ence o cPsp pνqsuch ha |A1`cB|δěδ´ǫ|A1| o all A1ĂA
wi h |A1| ě p1´ρq|A|. I u ns ou ha his innocen -looking di e ence makes Theo em
3.15 di icul o p o e wi h a di ec assaul . The e o e, we need a inal educ ion o he
ollowing s a emen :
Theo em 3.28. Le 0ăβďαă1and κą0. Then, o e e y γP ppα´βq{p1´βq,1s,
he e exis ǫ, ǫ0, ǫB, δ0P p0,1
2s, depending only on α, β, γ, κ, such ha he ollowing holds. Le
δP2´Nwi h δP p0, δ0s, and le A, B Ă pδ¨ZqX 0,1ssa is y he ollowing hypo heses:
(A) |A| ď δ´α.
(B) |B| ě δ´β, and Bsa is ies he ollowing F os man condi ion:
|BXBpx, q| ď κ|B|, δ ď ďδǫ0.
Assume mo eo e ha |B`B| ď δ´ǫB|B|.
Fu he , le νbe a Bo el p obabili y measu e wi h sp pνq Ă ´1,1ssa is ying he F os man
condi ion νpBpx, qq ď 40 ¨ γ o xPRand ěδ. Then, he e exis s a poin cPsp pνqsuch
ha |A`cB|δěδ´ǫ|A|.
Theo em 3.28 only di e s om Theo em 3.15 in i s (supe icially) weake conclusion,
and in ha he F os man cons an o νhas inc eased om 20 o 40.
P oo o Theo em 3.15 assuming Theo em 3.28.Fix he pa ame e s 0ăβďαă1,κ, and
γą pα´βq{p1´βq om Theo em 3.15. As usual, ou ask is o ind he pa ame e s
ǫ, ǫ0, ǫB, δ0, ρ such ha Theo em 3.15 is sa is ied. In doing so, we apply Theo em 3.28 o
he pa ame e s 0ăβď¯αă1and κ, whe e ¯αP pα, 1qis a bi a y such ha he key
inequali y γą p¯α´βq{p1´βqs ill holds. Then, we le
¯ǫ, ¯ǫ0,¯ǫB,¯
δ0ą0(3.29)
be he cons an s gi en by Theo em 3.28 wi h pa ame e s ¯α, β, κ, γ. We now begin de in-
ing he pa ame e s ǫ, ǫ0, ǫB, δ0, ρ. We se
ǫ0:“¯ǫ0and ǫB“¯ǫB.(3.30)
We will need ha δ0ď¯
δ0, and he e will be an addi ional (simple) dependences on he
allowed pa ame e s, which will be explained when hey a ise. To de ine he pa ame e s
ǫ, ρ, ix a na u al numbe N„1{¯ǫ, so ha he ollowing holds:
pN´1q´1ă¯ǫ{2.(3.31)
Then, le
ǫ:“¯α´α
2N`1.(3.32)
18 TUOMAS ORPONEN
Finally, de ine ρą0, depending only on ¯ǫ, so small ha
`2p1´p1´ρqNq˘1{2N
ď1
2.(3.33)
This is possible, since he inequali y is clea ly ue o ρ“0.
We now make he coun e assump ion ha Theo em 3.15 ails o ce ain δP p0, δ0s,
A, B Ă pδ¨Zq X 0,1s, and a Bo el p obabili y measu e νon ´1,1s, sa is ying he hy-
po heses o Theo em 3.15 wi h pa ame e s α, β, κ, γ, and he cons an s ǫ0, ǫ, δ0desc ibed
abo e. This means ha o e e y cPC“sp pνq, he e exis s a subse AcĂAwi h he
p ope ies
|Ac| ě p1´ρq|A|and |Ac`cB|δďδ´ǫ|A|.(3.34)
The plan is o use his in o ma ion o cons uc a new se ¯
AĂ pδ¨ZqX 0,1s, and a new
p obabili y measu e ¯νon ´1,1s, such ha he iple ¯
A, B, ¯νsa is ies he hypo heses o
Theo em 3.28 wi h pa ame e s ¯α, β, κ, γ and cons an s ¯ǫ0,¯ǫB, bu ne e heless |¯
A`cB| ă
δ´¯ǫ|¯
A| o all cPsp p¯νq. This con adic ion will comple e he p oo o Theo em 3.15.
Gi en such a se AcĂA o e e y cPC, we obse e ha
ż...ż|Ac1X...XAcN|dνpc1q¨¨¨dνpcNq ě p1´ρqN|A|(3.35)
by Hölde ’s inequali y. Conside he se
Ω :“ pc1,...,cNq P CN:|Ac1X...XAcN| ě 1
2|A|u.
I "I" empo a ily s ands o he in eg al in (3.35), we ha e
p1´ρqN|A| ď IďνNpΩcq¨ 1
2|A|`p1´νNpΩcqq¨|A|,
which can be ea anged o νNpΩcq ď 2p1´p1´ρqNq. Consequen ly
νNpΩq ě 1´2p1´p1´ρqNq “: 1 ´θ0.(3.36)
Fo c1,...,cnPC ixed, we de ine
Ωc1¨¨¨cn:“ pcn`1,...,cNq P CN´n:pc1,...,cNq P Ωu.
I ollows om Fubini’s heo em ha
νN´npΩc1¨¨¨cnq “ żνN´n´1pΩc1¨¨¨cncqdνpcq(3.37)
o all c1,...,cnPC, and 1ďnďN´2. The same emains ue o n“0, i he le
hand side is in e p e ed as νNpΩq. Equa ion (3.37) also emains alid o n“N´1i we
de ine he no a ion νN´n´1“ν0as ollows:
ν0pΩc1¨¨¨cN´1cq:“1Ωpc1,...,cN´1, cq.(3.38)
We will use his no a ion in he sequel.
Fo pc1,...,cNq P Ω ixed, we w i e
Ac1¨¨¨cN:“Ac1X...XAcNùñ |Ac1¨¨¨cN| ě 1
2|A|.(3.39)
We now cons uc a sequence o se s HnĂδ¨Z,1ďnďN. A he same ime, we will
cons uc subse s C1,...,CNĂC, and poin s cnPCn,1ďnďN, wi h he p ope ies
νN´npΩc1¨¨¨cnq ě 1´θnand νpCnq ě 1´θn,1ďnďN, (3.40)
whe e we de ine induc i ely
θn:“aθn´1ěθn´1.
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 19
In pa icula , he i s pa o (3.40) wi h n“Nshows ha pc1,...,cNq P Ω, ecall he
no a ion (3.38). As a second ema k, ecalling he de ini ion o θ0“2p1´p1´ρqNq, and
combining his wi h he de ini ion o ρin (3.33), one sees ha θnď1
2 o all 1ďnďN.
To begin wi h, we de ine
C1:“ cPC:νN´1pΩcq ě 1´θ1u,
and we choose an a bi a y elemen c1PC1. Since
1´θ0ďνNpΩq “ żνN´1pΩcqdνpcq ď νpCc
1q¨p1´θ1q`p1´νpCc
1qq “ ´θ1¨νpCc
1q`1
by (3.36), we obse e ha νpCc
1q ď θ0{θ1“θ1, and consequen ly νpC1q ě 1´θ1. In
pa icula C1‰ H. We hen de ine
H1:“ pc1Bqδ.
Assume induc i ely ha H1,...,Hnand C1,...,CnĂC, and cjPCj,1ďjďnďN´1,
ha e al eady been cons uc ed, and sa is y (3.40). We pick an elemen cn`1PCn`1, whe e
Cn`1:“ cPC:νN´n´1pΩc1¨¨¨cncq ě 1´θn`1u,1ďnďN´1.
Fo n“N´1, he no a ion νN´n´1pΩc1¨¨¨cncqshould be in e p e ed as in (3.38), so
CN“ cPC:1Ωpc1,...,cN´1, cq ě 1´θNu “ cPC:pc1,...,cN´1, cq P Ωu.
Fo an a bi a y choice cn`1PCn`1, we no e ha he i s pa o (3.40) is sa is ied wi h
index "n`1", by he de ini ion o Cn`1.
The se Cn`1also sa is ies he second pa o (3.40) wi h index "n`1", since
1´θn
(3.40)
ďνN´npΩc1¨¨¨cnq(3.37)
“żνN´n´1pΩc1¨¨¨cncqdνpcq ď ´θn`1¨νpCc
n`1q`1,
and consequen ly νpCc
n`1q ď θn{θn`1“θn`1, and νpCn`1q ě 1´θn`1.
Whe eas c1PC1was chosen a bi a ily, he elemen cn`1PCn`1is chosen in such
a way ha he quan i y |Hn`cn`1B|δis maximised, among all possible choices cn`1P
Cn`1. We hen de ine
Hn`1:“Hn`pcn`1Bqδ.
Con inuing in his manne p oduces a dis inguished sequence pc1,...,cNq P Ω, which
we ix o he emainde o he a gumen , and a sequence o se s H1,...,HN.
No e ha HnĂ pδ¨Zq X 0, Ns o all 1ďnďNby a s aigh o wa d induc ion,
so |Hn| ď 2Nδ´1. The e o e, by he pigeonhole p inciple, he e exis s an index nP
1,...,N ´1usuch ha
|Hn`1| ď p2Nδ´1q1{pN´1q|Hn| ď 4δ´1{pN´1q|Hn|.(3.41)
Fo his pa icula index nP 1,...,N ´1u, we hen ha e |Hn`cB|δ.|Hn`1| ď
4δ´1{pN´1q|Hn| o all cPCn`1by he de ini ion o Hn`1, and he e o e
|Hn`cB|δďδ´¯ǫ{2|Hn|, c PCn`1,(3.42)
ecalling (3.31), and assuming ha δą0is small enough.
We now claim ha (3.42) iola es Theo em 3.28 wi h pa ame e s ¯α, β, κ, γ, and wi h
he objec s
¯
A:“Hn, B, and ¯ν:“νpCn`1q´1¨ν|Cn`1.(3.43)
We need o check he ollowing i ems o con adic Theo em 3.28:
20 TUOMAS ORPONEN
(a) |¯
A| ď δ´¯α,
(b) |B| ě δ´βand |B`B| ď δ´¯ǫB|B|, and Bsa is ies a F os man condi ion wi h
exponen s κand ¯ǫ0,
(c) ¯νsa is ies a F os man condi ion wi h exponen γand cons an 40.
Poin (b) is ue by assump ion (and since we chose ǫB“¯ǫBand ǫ0“¯ǫ0in (3.30)), so only
(a) and (c) need o be e i ied. We i s use he Plünnecke-Ruzsa inequali y o es ablish
(a), assuming ha δą0is su icien ly small in e ms o N, ¯α. Clea ly ¯
Acan be w i en as
a sum o nďNse s o he o m pcmBqδ, o some 1ďmďn, whe e cmis an index in
he ( ixed) sequence pc1,...,cNq P Ω. No ing ha Ac1¨¨¨cNĂAcmĂA, each o hese se s
indi idually sa is ies
|Ac1¨¨¨cN`pcmBqδ|.|Acm`cmB|δ
(3.34)
ďδ´ǫ|A|(3.39)
ď2δ´ǫ|Ac1¨¨¨cN|.
We may he e o e in e ha
|¯
A|.N,ρ δ´2Nǫ|A| ď δ´2Nǫ´α.
om Lemma 3.3. This inequali y implies |¯
A| ď δ´¯α o small enough δą0, ecalling ou
choice o ǫa (3.32).
We mo e o (c). Recalling (3.43), and om (3.40) ha νpCn`1q ě 1´θNě1
2, we ha e
¯νpBpx, qq ď 2¨νpBpx, qq ď 40 ¨ γ, x PR, ěδ.
We ha e now eached a si ua ion which iola es Theo em 3.28 o he choice o pa am-
e e s ¯α, β, κ, γ: he objec s ¯
A, B, ¯νsa is y all he hypo heses (by (a)-(c)), bu ne e heless
we ha e |¯
A`cB|δďδ´¯ǫ|¯
A| o all cPCn`1, a se o ull ¯νmeasu e, by (3.42). This iola es
Theo em 3.28, since ¯ǫą0was he cons an associa ed o ¯α, β, κ, γ. The e o e he coun e
assump ion (3.34) is alse, and he p oo o Theo em 3.15 is comple e.
To be p ecise, we ha e igno ed ha ¯
AĂ 0, Nsins ead o ¯
AĂ 0,1s. This can be deal
wi h as in he p oo o Co olla y 1.11, o below (3.12). We lea e his o he eade .
3.4. Bonus educ ion. We ha e now educed he p oo o Theo em 1.8 o he p oo o
Theo em 3.28. Fo no a ional con enience in he u u e, we men ion one inal educ ion:
we may assume ha 1Psp pνq. Indeed, assume ha Theo em 3.28 is known unde
his ex a assump ion. Then, le A, B, ν be a gene al iple as in Theo em 3.28. Since
νis a p obabili y measu e, sp pνq Ă ´1,1sand νpBpx, qq ď 40 ¨ γ, he poin c0P
sp pνqX ´1,1swi h maximal absolu e alue sa is ies
|c0| ě 40´1{γ.
Conside he measu e ¯νpAq:“νpc0Aq. Obse e ha ¯νpBpx, qq ď 40 ¨ γand sp p¯νq “
c´1
0sp pνq. The e o e 1Psp p¯νq Ă ´1,1s, so ¯νsa is ies he ex a assump ion. We hen
apply he (assumedly known) e sion o Theo em 3.28 o A, pc0Bqδ,¯ν. The se pc0Bqδwill
ha e sligh ly wo se cons an s han B, in a manne depending on γonly, so he heo em
needs o be applied wi h app op ia ely modi ied pa ame e s. Once his has been done,
we ind a poin c“c´1
0c1Psp p¯νq, whe e c1Psp pνq, such ha
|A`cB|δ&|A`pc1{c0q¨pc0Bqδ|δ“ |A`cpc0Bqδ|δěδ´ǫ|A|,
and he p oo o Theo em 3.28 (wi hou he ex a assump ion) is comple e.
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 21
4. PROOF OF THEOREM 3.28
4.1. P elimina ies. We ha e now educed he p oo o Theo em 1.8 o he p oo o The-
o em 3.28. We ix he pa ame e s α, β, γ, κ, wi h 0ăβďαă1and pα´βq{p1´βq ă
γď1. We also ix se s A, B Ă pδ¨Zq X 0,1sand a Bo el p obabili y measu e νwi h
sp pνq Ă ´1,1s, sa is ying all he hypo heses o Theo em 3.28 wi h su icien ly small
cons an s ǫ0, ǫBą0 o be de e mined la e . Fo u u e e e ence, we w i e
|A| “:δ´¯α,0ď¯αďα. (4.1)
We make a coun e assump ion: |A`cB|δăδ´ǫ|A| o all cPsp pνq. Since we may
assume ha 1Psp pνqby Sec ion 3.4, we ha e he assump ions
|A`B| ď δ´ǫ|A|and |B`B| ď δ´ǫB|B|.(4.2)
I ǫ, ǫBą0in (4.2) a e small enough, depending only on α, β, κ, γ, we will be able o
ind a poin cPsp pνqsuch ha |A`cB|δěδ´ǫ|A|. This will iola e he coun e as-
sump ion, and p o e Theo em 3.28. The necessa y alues o ǫ“ǫpα, β, γ, κq ą 0and
ǫB“ǫBpα, β, γ, κq ą 0in (4.2) will be ixed du ing he p oo o P oposi ion 4.12.
4.2. Shme kin’s in e se heo em. In he case A“B, Bou gain [5] used an assump ion
o he o m (4.2) o ob ain, up o passing o a subse , a special mul i-scale s uc u e inside
A: in o mally speaking, when passing om one scale o he nex , ei he Ahas ull b anch-
ing, o hen no b anching. Simila s a emen s ha e, a e Bou gain’s wo k, been p o ed by
Hochman [19] and Shme kin [34] in he case whe e A‰B, and whe e Aand Bmay ha e
comple ely di e en sizes. This is ou si ua ion, and we will apply Shme kin’s heo em,
which we s a e in Theo em 4.6.
De ini ion 4.3 (δ-se s and measu es, L2-no ms).Le δP2´Nbe a dyadic a ional. A
subse o pδ¨Zq X 0,1qis called a δ-se . A p obabili y measu e suppo ed on a δ-se is
called a δ-measu e. The L2-no m o a δ-measu e µis de ined by
}µ}L2:“˜ÿ
zPδ¨Z
µp zuq2¸1{2
.
We will only be conce ned wi h δ-measu es o he o m µ“ |A|´1H0|A, whe e AĂ
0,1qis a δ-se . Then }µ}L2“ |A|´1{2.
De ini ion 4.4 (Uni o m se s).Le m, N PN, and se δ:“2´mN P2´N. Fo AĂ 0,1qand
sP 0,...,N ´1u, w i e ImspAq:“ IPDms :AXI‰ Hu o he collec ion o dyadic
in e als o side-leng h 2´ms ( hese a e deno ed Dms) wi h non-emp y in e sec ion wi h
A. We say ha Ais pm, Nq-uni o m i
RApsq:“ |IXA|2´mps`1q, I PImspAq,
is independen o he choice o IPImspAq. We may also w i e ha Ais pm, N, RAq-
uni o m i he b anching numbe s RAneed emphasising.
In he de ini ion o RApsq, is i impo an o emembe ha |H| is, by de ini ion, he
numbe o dyadic -in e als in e sec ing H– ins ead o he -co e ing numbe . This
dis inc ion has ha dly ma e ed ea lie in he pape .
As in [34], we will only conside uni o m se s which a e also δ-se s. I was obse ed by
Bou gain [5] ha e e y δ-se con ains a uni o m subse o "compa able" ca dinali y. Thus,
22 TUOMAS ORPONEN
he possibili y o inding uni o m subse s has no hing o do, ye , wi h an assump ion like
(4.2). To explain wha (4.2) implies, we in oduce he ollowing e minology:
De ini ion 4.5 (η-pola ised pai ).Le m, N PN,δ“2´mN , and ηą0. A pai o pm, Nq-
uni o m se s pA, Bqis pη, m, Nq-pola ised, i
RBpsq ą 1ùñ RApsq ě 2p1´ηqm, s P 0,...,N ´1u.
I A“B, we say ha A(ins ead o pA, Aq) is pη, m, Nq-pola ised.
No e ha RApsq ď 2m o all sP 0,...,N ´1u, so RApsq ě 2p1´ηqmmeans ha
RApsqis nea ly maximal. Bou gain [5] p o ed ha i Ais a δ-se wi h |A`A| ď δ´ǫ|A|,
hen Acon ains a uni o m subse A1such ha |A1| ě δη|A|, and A1is η-pola ised, whe e
η“oǫp1q. This means ha ei he RA1psq “ 1o RA1psq ě 2p1´ηqm o all scales "s".
Ve sions o Bou gain’s "pola isa ion heo em", explained abo e, o wo di e en se s
we e ound by Hochman [19] and Shme kin [34]. Hochman i s showed ha i µ, ν a e
p obabili y measu es on 0,1q, hen he en opy inequali y Hpµ˚νq ď Hpµq `ǫimplies
a measu e- heo e ic e sion o he pola isa ion phenomenon o µ, ν. The se e sion,
below, was es ablished by Shme kin [34] (wi h a p oo e y di e en om [19]):
Theo em 4.6 (Shme kin).Le ηą0, and le mpηq P Nbe su icien ly la ge, depending on η.
Then, o all měmpηq he e exis s ǫ“ǫpη, mq ą 0such ha he ollowing holds o all la ge
enough NPN. Le δ“ p2´mqN, and le A, B Ă 0,1sbe δ-se s such ha
|A`B| ď δ´ǫ|A|.
Then, he e exis pm, Nq-uni o m se s A1ĂAand B1ĂBsuch ha |A1| ě δη|A|,|B1| ě δη|B|,
and pA1, B1qis pη, m, Nq-pola ised.
Rema k 4.7.To be accu a e, Theo em 4.6 is a sligh e inemen o Shme kin’s heo em: [34,
Theo em 2.1] li e ally con ains he ollowing s a emen : i ηą0and m0PN, hen he e
exis s m“mpη, m0q ě m0and ǫ“ǫpη, m0q ą 0as in Theo em 4.6.Howe e , i one inspec s
he p oo o [34, Theo em 2.1], one obse es ha he only dependence o m“mpη, m0q
on m0is "měm0", and any choice o měm0wo ks, p o ided ha mis also su icien ly
la ge in e ms o η. This is p ecisely wha Theo em 4.6 says.
As ano he ema k, Shme kin’s heo em ac ually conce ns a pai o δ-measu es µ1, µ2
ins ead o δ-se s: he measu es o in e es o ou applica ion a e simply µ1“ |A|´1H0|A
and µ2“ |B|´1H0|B, and wi h such choices [34, Theo em 2.1] implies Theo em 4.6.
Rema k 4.8.We will be applying Theo em 4.6 o dyadic scales o he o m δ“2´ℓmN ,
whe e ℓ, m, N PN. Since δ“ p2´mqℓN “ p2´ℓmqN, a δ-se AĂ 0,1qmay be pm, ℓNq-
uni o m, pℓm, Nq-uni o m, o bo h. The o me condi ion means ha he b anching num-
be s Rm
Apsq “ |AXI|2´mps`1qa e well-de ined o mP ℓNs, whe eas he la e means ha
he b anching numbe s Rℓm
Apσq “ |AXI|2´ℓmpσ`1qa e well-de ined o σP Ns. I is clea
ha e e y pm, ℓNq-uni o m 2´ℓmN -se is pℓm, Nq-uni o m, and indeed
Rℓm
Apσq “
ℓpσ`1q´1
ź
s“ℓσ
Rm
Apsq, σ P Ns.
The con e se is gene ally no ue, so pm, ℓNq-uni o mi y is a s ic ly s onge p ope y
han pℓm, Nq-uni o mi y. We will also be in e es ed in pai s pA, Bqwhich a e some imes
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 23
pη, m, ℓNq-pola ised, and some imes pη, ℓm, Nq-pola ised. In con as o uni o mi y, he e
is no simple implica ion be ween hese wo p ope ies.
In addi ion o Shme kin’s heo em, we will also need a lemma om i s p oo :
Lemma 4.9. Le m, ℓ, N PN,δ“2´ℓmN , and le AĂ 0,1qbe an pm, ℓNq-uni o m δ-
se . Then Ais also pℓm, N, Rℓm
Aq-uni o m o some RA: Ns Ñ 1,...,2ℓmu. I SĂ Nsis
a bi a y, he e exis s A1ĂAwhich is pm, ℓNq-uni o m, and also pℓm, N, Rℓm
A1q-uni o m wi h
|A1| ě |A|¨ ź
σPS
Rℓm
Apσq´1,and Rℓm
A1pσq “ #1, σ PS,
Rℓm
Apσq, σ RS.
A simila s a emen holds ue i SĂ ℓNs, wi h he only di e ence ha "Rℓm
Apσq" and "Rℓm
A1pσq"
should be eplaced by "Rm
Apsq" and "Rm
A1psq" o sP ℓNs.
The lemma abo e is [34, Lemma 3.7]. To be accu a e, he s a emen abou A1 emaining
pm, ℓNq-uni o m is no pa o he s a emen o [34, Lemma 3.7], bu he 3.8-line p oo
quickly e eals ha pm, ℓNq-uni o mi y is no iola ed when passing be ween Aand A1;
he only poin is o "collapse" all he b anching o A o le els co esponding o σPS, o
equi alen ly o sP ℓσ, ℓpσ`1q´1u o all σPS.
4.3. Applying he in e se heo em. We s a by ixing he ollowing pa ame e s:
$
’
&
’
%
ℓ“ℓpα, β, γ, κq P N,
η“ηpα, β, γ, κq P p0,1q,
m0PNwi h m0ě p40 `C0q{η.
(4.10)
He e C0ą0is an absolu e cons an o be speci ied la e . In ac , he alues o all
hese cons an s will be speci ied la e , bu as indica ed abo e, all o hem only depend
on α, β, γ, κ. Fo he eade in e es ed in seeing speci ic choices, we e e o (4.23) and
he discussion a e wa ds. Recall ha he se Bsa is ies he F os man condi ion |BX
Bpx, q| ď κ|B| o all δď ďδǫ0, whe e we may eely choose ǫ0“ǫ0pα, β, κ, γq ą 0.
We choose
ǫ0:“η. (4.11)
We will assume ha η, ǫ, ǫBă1{1000 in he sequel (bu hese uppe bounds will gene ally
no su ice). This sec ion is de o ed o he p oo o he ollowing p oposi ion, whose
p oo will also inalise he choice o he pa ame e s ǫ, ǫBą0, ela i e o η:
P oposi ion 4.12. The e exis ǫ, ǫBą0and měm0, depending on α, β, γ, κ, such ha he
ollowing holds o all δP2´No he o m δ“2´ℓmN ,NPN. Assume ha A, B Ă 0,1s
a e δ-se s sa is ying he small doubling assump ions (4.2). Then he e exis subse s A1ĂAand
B1ĂBwi h he ollowing p ope ies:
(1) A1and B1a e pm, ℓNq-uni o m wi h |A1| ě δη|A|and |B1| ě δη{2|B|.
(2) The pai pA1, B1qis pη, m, ℓNq-pola ised.
(3) The se B1is pη{2, ℓm, Nq-pola ised.
Rema k 4.13.In he sequel, we will always wo k wi h scales o he o m δ“2´ℓmN wi h
he ixed pa ame e s ℓ, m, which depend on α, β, γ, κ. In o he wo ds, we ini ially p o e
Theo em 3.28 (and ind he cons an s ǫ, ǫ0, ǫB) o only scales o his special o m. A e
his has been accomplished, i is easy o check ha he case o gene al scales δP2´Nis a
24 TUOMAS ORPONEN
co olla y, assuming ha he uppe bound δ0“δ0pα, β, γ, κq ą 0 o δis su icien ly small.
The eason is ha i δP2´Nis a bi a y, hen he e exis s a scale o he o m ¯
δ“2´ℓmN
wi h δď¯
δ.α,β,γ,κ δ. We lea e he es o his educ ion o he eade .
As ano he ema k, we will la e in he pape need o assume ha ǫ“ǫpα, γq ą 0is
su icien ly small ha ǫ
1´α´ǫďγ
2.(4.14)
This equi emen should be combined wi h he one coming om P oposi ion 4.12.
P oo o P oposi ion 4.12.We begin by applying Theo em 4.6 wi h cons an η3ą0 o he
pai pB, Bq, o which we assumed in (4.2) ha |B`B| ď δ´ǫB|B|. Assume ha mě
mpη3q P Nis su icien ly la ge ha Theo em 4.6 applies. Assume addi ionally ha mě
m0, whe e m0is he cons an om (4.10). Then, i ǫB“ǫBpη3, ℓmq “ ǫBpα, β, γ, κq ą 0
and δ“ p2´ℓmqNa e su icien ly small, we ind an pℓm, Nq-uni o m subse B1ĂBsuch
ha |B1| ě δη3|B|, and B1is pη3, ℓm, Nq-pola ised. We ha e now ixed he alue o he
pa ame e ǫBą0in (4.10)(and hence in Theo em 3.28)!
Nex , no e ha |A`B1| ď |A`B| ď δ´ǫ|A|. We he e o e may apply Theo em 4.6
again o he pai pA, B1q, again wi h pa ame e η3ą0. I ǫ“ǫpη3, mq ą 0is su icien ly
small, we ind an pm, ℓNq-uni o m subse A1ĂAwi h |A1| ě δη3|A| ě δη|A|, and an
pm, ℓNq-uni o m subse B2ĂB1such ha
|B2| ě δη3|B1|,(4.15)
and pA1, B2qis pη3, m, ℓNq-pola ised. In pa icula pA1, B2qis pη, m, ℓNq-pola ised. We
ha e now ixed he alue o he pa ame e ǫą0in (4.2)!
A e we done wi h p ope ies (1)-(3) in P oposi ion 4.12? No qui e: while passing om
B1 o B2, we migh ha e los he pη3, ℓm, Nq-pola isa ion o B1. The plan will be o pass
o a inal pm, ℓNq-uni o m subse B3ĂB2which is pη{2, ℓm, Nq-pola ised, and such ha
|B3| ě δη{4|B2|. Then inally
|B3| ě δη{4|B2| ě δη{4`η3|B1| ě δη{4`2η3|B| ě δη{2|B|.
Also pA1, B3q emains pη, m, ℓNq-pola ised, since his p ope y is no iola ed by eplac-
ing B2by an pm, ℓNq-uni o m subse , o example B3.
W i e
S0:“ σP Ns:Rℓm
B1pσq “ 1uand S1:“ σP Ns:Rℓm
B1pσq ě 2p1´η3qℓmu.
Since B1was cons uc ed o be pη3, ℓm, Nq-pola ised, we ha e Ns “ S0YS1, and
|B1| “ ź
σPS1
Rℓm
B1pσq ě 2p1´η3qℓm|S1|.
Now, le Sbad :“ σPS1:Rℓm
B2pσq ă 2p1´η{2qℓmu, and Sgood :“S1zSbad. (No e ha he
numbe s Rℓm
B2pσqa e well-de ined, since B2is pm, ℓNq-uni o m, hence pℓm, Nq-uni o m.)
Then, since e iden ly Rℓm
B2pσq ď Rℓm
B1pσq “ 1 o all σPS0, we ha e
|B2| “ ź
σPSbad
Rℓm
B2pσq¨ ź
σPSgood
Rℓm
B2pσq ď 2p1´η{2qℓm|Sbad |¨2ℓmp|S1|´|Sbad|q
“2ℓm|S1|´pη{2qℓm|Sbad|.
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 31
whe e Γwas de ined in (4.29). In pa icula , ξ&α,β,γ 1. We also impose he ollowing
addi ional condi ion on he cons an ℓPNselec ed a (4.10):
ℓěξ´1“4
γ´Γ.(4.37)
Recall ha J“ ´ ,..., u P N`was he sho es ex ension ( o he le ) o a ce ain
in e al J0PℓNB1wi h he p ope y Rm
B1pJq ě 2ζm|J|“2ζmp `1q. Consequen ly, he
subin e al Jξ“ ´ p1´2ξq u,..., udoes no ye ha e his p ope y, ha is,
Rm
B1pJξq ă 2ζm|Jξ|“2ζmp p1´2ξq u`1q.(4.38)
He e we used ha p1´2ξq uă , which is ue because ξ ěξℓ ě1by (4.37).
Now, i ollows om a combina ion o (4.38), and Rm
B1pJq ě 2ζm|J|“2ζmp `1q, ha
Rm
B1pJzJξq ě 2ζmp ´ p1´2ξq uqě22ξζm ě2ξζmp `1q“2ξζm|J|.(4.39)
We a e hen p epa ed o de ine he desi ed subse B2ĂB1. Le Sξ:“ Y Jξ:JPN`u,
and apply he "collapsing" Lemma 4.9 o he pm, ℓNq-uni o m se B1, and he se o scales
SξĂ ℓNs. The p oduc is an pm, ℓNq-uni o m subse B2ĂB1such ha
Rm
B2psq “ #Rm
B1psq, s RSξ,
1, s PSξ.
In pa icula , Rm
B2psq “ Rm
B1psq o all sPJzJξ, o JPN`, so (4.39) emains alid o
he se B2:
Rm
B2pJq ě Rm
B1pJzJξq ě 2ξζm|J|.(4.40)
In ac , he i s inequali y is an equa ion, since Rm
B2psq “ 1 o all sPJξĂSξ. Cu iously,
we will ha e no use o a "global" lowe bound o |B2|, al hough i would be easy o
deduce om (4.28) ha |B2| ě δ2ζ¨ |B1|. F om now on, only he "local" b anching es i-
ma e (4.40) will be needed, and "global" lowe bound |B1|'δ´βhas al eady been ully
exploi ed in p e ious sec ions (whe e he ela ion be ween γ, α and βappea ed).
The poin o educing B1 o B2was o imp o e he 2´mp `1q-sepa a ion o dis inc in-
e als IPImp `1qpB1q o some hing esembling 2´mp ´ q-sepa a ion. This has now been
accomplished. Mo e p ecisely, assume ha J“ ´ ,..., u P N`, le IPImp ´ qpB2q,
and and le I1, I2PImp `1qpB2qbe dis inc . Then, since
Rm
B2psq “ 1, s PJξ“ ´ p1´ξq u,..., u,
he in e als I1, I2a e con ained inside dis inc in e als
ˆ
I1,ˆ
I2PImp ´ p1´ξq uqpB2q Ă Imp ´ p1´ξq uqpB1q.
Consequen ly, using also ha p1´ξq uě p1´ξq ´1, and ξ ěξℓ ě1,
dis pI1, I2q ě dis pˆ
I1,ˆ
I2q(4.17)
ě2´mp ´ p1´ξq uq
ě2´ξm ´m¨2´mp ´ q
ě2´2ξmp `1q¨2´mp ´ q.(4.41)
Inequali y (4.41) is mo e clea ly ph ased in he ollowing way:
32 TUOMAS ORPONEN
Lemma 4.42. Le J“ ´ ,..., u P N`,∆J:“2´mp ´ q, and δJ:“2´mp `1q. Le
IPImp ´ qpB2qbe a dyadic in e al o leng h ∆Jin e sec ing B2, and le I1, I2PImp `1qpB2q
be dis inc wi h I1, I2ĂI. Then,
dis pI1, I2q ě ˆδJ
∆J˙2ξ
¨|∆J|.
P oo . Obse ing ha δJ{∆J“2´mp `1q, his inequali y is jus a ewo ding o (4.41).
4.8. Elemen a y p ojec ion es ima es. The plan is o p o e lowe bounds o |A1`cB2|δ
by, oughly speaking, es ablishing sepa a ely lowe bounds o |pA1XIq` cpB2XJq|δ,
whe e I, J Ă 0,1qa e sui able dyadic in e als in e sec ing A1, B2, and hen combining
he esul s. In his sec ion, we will p o e an auxilia y esul which will imply he equi ed
lowe bounds o |pA1XIq`cpB2XJq|δ. To be mo e accu a e, ins ead o p o ing lowe
bounds o |pA1XIq ` cpB2XJq|δdi ec ly, we p o e (s onge ) lowe bounds o he
en opies o sui able measu es suppo ed on pA1XIq ` cpB2XJq(see (4.58)). This is
(only!) done o he eason ha such "mul i-scale" in o ma ion abou en opy is cleane
o combine han "mul i-scale" in o ma ion abou ca dinali ies.
We in oduce he ollowing no a ion. Dyadic cubes in Rdo side-leng h 2´na e de-
no ed Dn. I µis a Bo el p obabili y measu e on Rd, and nPN, we w i e
µpnq:“ÿ
QPDn
µpQq
LdpQq¨Ld|Q.
Thus µpnqis a "2´n-disc e isa ion o µ". No e ha µpnqPL2pRdqXL8pRdq. We also de ine
he p ojec ions πcpx, yq:“x`cy o px, yq P R2and cPR.
Lemma 4.43. Le ∆“2´nP2´N, and le γ, γA, γBP p0,1s, and Cě1. Le A,BĂDnbe
collec ions o dyadic ∆-in e als wi h |A| “ ∆´γAand |B| “ ∆´γB. We assume he ollowing
sepa a ion om B, o some ξP p0,1s:
dis pI1, I2q ě ∆ξ o dis inc I1, I2PB.(4.44)
Le
‚Le µbe a p obabili y measu e wi h sp µĂ pYAqˆpYBqwi h he p ope y ha µpQq ď
C∆γA`γB o QPDn.
‚Le νbe a p obabili y measu e on ´1,1ssuch ha νpIq ď C∆γ o all IPDn.
Then,
ż1
´1}pπcµqpnq}2
2dνpcq.C¨max ∆γA`γB´1,∆γ´1´ξu.(4.45)
Rema k 4.46.To help in e p e ing he uppe bound (4.45), le us men ion he " i ial"
es ima e }pπcµqpnq}2
2.∆γA´1 o e e y cP 0,1q. This could be deduced a he easily
om (4.47) below. The e o e, (4.45) bea s he i ial bound whene e γąγA`ξ.
P oo o Lemma 4.43.By de ini ion,
pπcµqpnq“ÿ
IPDn
πcµpIq
∆¨L1|I“ÿ
IPDn
µpπ´1
cpIqq
∆¨L1|I. c P ´1,1s.
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 33
Consequen ly,
}pπcµqpnq}2
2“ÿ
IPDnˆµpπ´1
cpIqq
∆˙2
¨∆“1
∆¨ÿ
IPDnpµˆµqp pp, qq:p, q Pπ´1
cpIquq.(4.47)
The e o e,
∆¨ż1
´1}pπcµqpnq}2
2dνpcq „ ż1
´1ÿ
IPDnpµˆµqp pp, qq:p, q Pπ´1
cpIquqdνpcq
“¨żÿ
IPDn
1 p,qPπ´1
cpIqupcqdνpcqdµppqdµpqq.
We spli he ou e in eg a ion in o
Ωnea :“ pp, qq:|p´q| ă 10∆uand Ω a :“ pp, qq:|p´q| ě 10∆u.
Rega ding Ωnea , we only use he obse a ion ha i p, q PAˆBand cP 0,1sa e ixed,
hen he e is a mos one in e al IPDnsuch ha p, q Pπ´1
cpIq. Since µ, ν a e p obabili y
measu es, and µpBpx, 10∆qq .C∆γA`γB o e e y xPR2, his leads o
¨Ωnea ÿ
IPDn
1 p,qPπ´1
cpIqupcqdνpcqdµppqdµpqq.pµˆµqpΩnea q.C∆γA`γB.(4.48)
We hen conside in eg al o e he domain Ω a . A basic, easy o e i y, obse a ion is
his: i p, q PR2a e ixed and dis inc , hen he se
Ipp, qq:“ cP 0,1s:p, q Pπ´1
cpIq o some IPDnu
is con ained in an in e al o leng h .∆{|p´q|, and in pa icula can be co e ed by
.|p´q|´1dyadic in e als o leng h ∆.
We combine his wi h he ollowing addi ional obse a ion. No e ha all he ubes
π´1
cpIqmake an angle ďπ{4wi h he y-axis ( his is a ained o c“1, and o c“0, he
ubes π´1
cpIqa e e ical). The e o e,
p, q PAˆB, |p´q| ě 10∆ and DcP ´1,1ss. . p, q Pπ´1
cpIq ùñ |py´qy| ą ∆.
He e py, qyPB e e o he second coo dina es o p, q. Namely, i |p´q| ě 10∆ and
|py´qy| ă ∆, hen |px´qx| ě 9∆, which makes he pai p, q oo "ho izon al" o be
con ained in any common ube π´1
cpIq, wi h cP ´1,1sand IPDn. Now, ecalling ou
assump ion (4.44) ha dis pI1, I2q ě ∆ξ o dis inc I1, I2PB, he conclusion |py´qy| ą ∆
can be ampli ied subs an ially: |py´qy| ą ∆implies ha py, qylie in dis inc in e als in
B, hence |p´q| ě |py´qy| ě ∆ξ. The e o e:
¨Ω a żÿ
IPDn
1 p,qPπ´1
cpIqupcqdνpcqdµppqdµpqq “ ¨ΩFAR żIpp,qq
. . . dνpcqdµppqdµpqq,
wi h ΩFAR “ pp, qq:|p´q| ě ∆ξu. Now, o e e y pai pp, qq P ΩFAR, we no e ha he
se Ipp, qq Ă 0,1scan be co e ed by .|p´q|´1ď∆´ξdyadic in e als o leng h ∆, and
o each cPIpp, qq, he e is exac ly one IPDnsuch ha p, q Pπ´1
cpIq. The e o e,
żIpp,qqÿ
IPDn
1 p,qPπ´1
cpIqupcqdνp q “ νpIpp, qqq .C∆γ´ξ,pp, qq P ΩFAR,
34 TUOMAS ORPONEN
and consequen ly
¨Ω a żÿ
IPDn
1 p,qPπ´1
cpIqupcqdνpcqdµppqdµpqq.C∆γ´ξ.
Combining his es ima e wi h (4.48), we a i e a (4.45).
We will nex deduce, as a co olla y, an en opy e sion o Lemma 4.43. Fo his pu -
pose, we eco d he ollowing [35, Lemma 3.6] by Shme kin:
Lemma 4.49. Le µbe a Bo el p obabili y measu e on Rd. The ollowing ela ion holds be ween
he Dn-en opy Hpµ, Dnqo µ, and he L2-no m o µpnq:
Hpµ, Dnq ě dn ´log }µpnq}2
2.(4.50)
He e, and below, "log" e e s o loga i hm in base 2.
Co olla y 4.51. Le ∆“2´nP2´N, and assume ha A,B, µ, ν, γA, γB, γ, C, and ξha e he
same meaning as in Lemma 4.43. Then,
ż1
´1
Hpπcµ, Dnqdνpcq ě n¨min γA`γB, γ ´ξu´log C´log C0,(4.52)
whe e C0ą0is an absolu e cons an .
P oo . Fi s combine (4.50) (wi h d“1) and Jensen’s inequali y o deduce ha
ż1
´1
Hpπcµ, Dnqdνpcq ě n´ż1
´1
log }pπcµqpnq}2
2dνpcq ě n´log ˆż1
0}pπcµqpnq}2
2dνpcq˙.
He e,
ż1
´1}pπcµqpnq}2
2dνpcq ď C0Cmax 2np1´γA´γBq,2np1`ξ´γqu
o some absolu e cons an C0ą0, by Lemma 4.43. These inequali ies gi e (4.52).
4.9. P ojec ing pieces o A1ˆB2.We nex pu Co olla y 4.51 o wo k in ou " eal-wo ld"
si ua ion. We ecall he ollowing no a ion om Sec ion 2.1. Assume ha µis a Bo el
p obabili y measu e on Rd(we will use his o bo h d“1and d“2), and le QPDnbe
a dyadic cube o side-leng h 2´nsuch ha µpQq ą 0. Le TQ:QÑ 0,1qdbe he escaling
map wi h TQpQq “ 0,1qd. We de ine he measu es
µQ:“1
µpQq¨µ|Qand µQ:“TQµQ.(4.53)
In his sec ion, µ“µA1ˆµB2, whe e µA1is he no malised coun ing measu e on A1, and
µB2is he no malised coun ing measu e on B2(de ined in Sec ion 4.7). Fo sP ℓNs, we
will w i e
Dmspµq:“ IˆJ:IPImspA1qand JPImspB2qu “ QPDms :µpQq ą 0u.
Fix
J“ ´ ,..., u P Nlow
`.
As de ined in (4.30), his means ha Rm
A1pJq ď 2Γm|J|, whe e ΓP ppα´βq{p1´βq, γq Ă
γ{2, γqwas he pa ame e speci ied in (4.29). Fo now, i is only impo an o emembe
ha γ´Γ&α,β,γ 1. Fix in e als I0PImp ´ qpA1qand J0PImp ´ qpB2q. W i e
AI0:“ I1PImp `1qpA1q:I1ĂI0uand BJ0:“ J1PImp `1qpB2q:J1ĂJ0u.
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 35
Then
|AI0| “ Rm
A1pJq ď 2Γm|J|and |BJ0| “ Rm
B2pJq(4.40)
ě2ξζm|J|.(4.54)
In pa icula , we may w i e
Rm
A1pJq “ |AI0| “ 2γAm|J|and |BJ0| “ 2γBm|J|(4.55)
o some 0ďγAďΓand γBěξζ. Then, w i e
Q0:“IˆJPDmp ´ qpµq, n :“m|J| “ mp `1qand ∆ :“2´n“2´mp `1q
2´mp ´ qěδ.
Conside he no malised measu e µQ0, as in (4.53). The measu e µQ0is suppo ed on a
p oduc o he o m pYAqˆpYBq “ TQ0ppYAI0qˆpYBJ0qq, whe e A,Ba e he amilies o
∆-in e als ob ained by no malising he in e als in AI0and BJ0by a ac o o 2mp ´ q. I
ollows om he pm, ℓNq-uni o mi y o A1and B2 ha
µQ0pQq ď p|A||B|q´1“ p|AI0||BJ0|q´1(4.55)
“∆γA`γB, Q PDn.
Mo eo e , he in e als in Bsa is y he ollowing sepa a ion p ope y by Lemma 4.42:
I1, I2PB, I1‰I2ùñ dis pI1, I2q ě ∆2ξ.
These ac s place us in a posi ion o apply Co olla y 4.51 o he measu e µQ0:
ż1
´1
HpπcµQ0,Dnqdνpcq ě n¨min γA`γB, γ ´2ξu´log 40 ´log C0.(4.56)
The pa ame e "ξ" was ini ially chosen (see (4.36)) so ha 2ξď pγ´Γq{2. Since γAďΓ,
his leads o
γ´2ξěγA`pγ´Γq´2ξěγA`pγ´Γq{2.
Recalling also ha γBěξζ by (4.54), and ζP p0,1q(see (4.22) o a eminde ), we ind
min γA`γB, γ ´2ξu ě min γA`ξζ, γA`pγ´Γq{2u “ γA`ξζ. (4.57)
Be o e he inal conclusion, le us ecall ha n“mp `1q “ m|J|, and obse e ha
γA¨n“γA¨m|J|(4.55)
“log Rm
A1pJq.
The e o e, (4.56)-(4.57) yield
ż1
´1
HpπcµQ0,Dm|J|qdνpcq ě n¨pγA`ξζq´log 40 ´log C0
“log Rm
A1pJq`ξζ ¨m|J|´log 40 ´log C0(4.58)
o all J“ ´ ,..., u P Nlow
`and o all Q0“IˆJPDmp ´ qpµq.
36 TUOMAS ORPONEN
4.10. Final mul iscale a gumen . As in he p e ious sec ion, le µA1be he no malised
coun ing measu e on he se A1, le µB2be he no malised coun ing measu e on he se B2,
and le µ“µA1ˆµB2. Recall also ha Dmspµq “ QPDms :µpQq ą 0u o sP ℓNs. We
wa n he eade ha he no a ion "Dms" will in his sec ion e e o bo h dyadic squa es
in R2, and dyadic in e als in R. The meaning should always be clea om con ex .
The pu pose o his sec ion is o show ha he e exis s cPsp pνqsuch ha
1
ℓmN ¨Hpπcµ, DℓmN q ě ¯α`ξζ ¨1
2 p1´βq´pα´βq{Γs´2η. (4.59)
He e ¯αwas he cons an (de ined in (4.1)) such ha |A| “ δ´¯α. The lowe bound in (4.59)
yields a lowe bound o |A1`cB2|δ, and consequen ly |A`cB|δ: since Hpπcµ, DℓmN q ď
log |A1`cB2|δďlog |A`cB|δ, and ℓmN “ ´log δ, we deduce om (4.59) ha
log |A`cB|δ
´log δě¯α`ξζ ¨1
2 p1´βq´pα´βq{Γs´2η.
I ηą0is su icien ly small, depending only on α, β, γ, κ, his implies |A`cB|δě
δ´¯α´η“δ´η|A|. O cou se i is impo an he e ha he alues o ξ“ pγ´Γq{4(see
(4.36)) and ζą0(see (4.22)) a e independen o ¯α, al hough hey may depend on α. This
p o es Theo em 3.28: ei he (4.2) ails, and |A`cB|δěδ´ǫ|A|wi h c“1Psp pνq, o
(4.2) holds, and in his case |A`cB|δěδ´η|A| o he poin cPsp pνqp o ided by (4.59).
I emains o p o e (4.59). This will be accomplished by combining (4.58) wi h he
ollowing uni o m lowe bound:
Lemma 4.60. Le J“ s, . . . , u Ă ℓNs, and le Q0PDmspµq. Then,
HpπcµQ0,Dm|J|q ě log Rm
A1pJq´1, c P 0,1s.(4.61)
P oo . Le IPImspA1qand JPImspB2qsuch ha Q0“IˆJ. Then µQ0“µI
A1ˆµJ
B2,
hence πcµQ“µI
A1˚µJ
B2, and inally
HpπcµQ0,Dm|J|q “ HpµI
A1˚µJ
B2,Dm|J|q ě żHppµI
A1qx,Dm|J|qdµJ
B2pxq,(4.62)
whe e he inequali y ollows om he conca i y o en opy (we discussed his a (2.5)),
and whe e pµA1qI
xpHq:“µI
A1pH´xq o HĂR. F om he de ini ion o en opy, one has
HppµI
A1qx,Dm|J|q “ HpµI
A1,Dm|J|´xq,
whe e Dm|J|´x e e s o he amily o p´xq- ansla ed dyadic in e als. Now, o xPR
ixed, e e y in e als in Dm|J|can be co e ed by 2in e als in Dm|J|´xand ice e sa.
This implies ha
|HpµI
A1,Dm|J|´xq´HpµI
A1,Dm|J|q| ď log 2 “1, x PR.(4.63)
Fu he mo e, by de ini ion,
HpµI
A1,Dm|J|q “ ´ ÿ
LPDm|J|
µI
A1pLqlog µI
A1pLq.
Since A1is pm, ℓN, Rm
A1q-uni o m, ei he µI
A1pLq “ 0, o hen µI
A1pLq “ Rm
A1pJq´1 o e e y
LPDm|J|. The e o e
HpµI
A1,Dm|Jq “ Rm
A1pJq´1.
In combina ion wi h (4.62)-(4.63), his yields (4.61).
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 37
Recall he in e als Nlow
`ĂN`, de ined in (4.30). In his sec ion, he p ope ies o
hese in e als will be used ia he o mula (4.58), and we addi ionally need o ecall ha
ÿ
JPNlow
`
|J| ě 1
2 p1´βq´pα´βq{Γs¨ℓN (4.64)
by (4.31). Le Pbe he pa i ion o ℓNswhich is induced by he in e als in Nlow
`. In o he
wo ds, Pconsis s o he in e als in Nlow
`, and he maximal complemen a y in e als. We
w i e
Puseless :“PzNlow
`,
and we enume a e P“ J1,J2,...,Jhu, whe e 1ďhďℓN. We w i e Jj“ sj,..., ju
o 1ďjďh, so s1“0, h`1“ℓN, and sj`1“ j`1 o all 1ďjăh. We a i icially
de ine sh`1:“ℓN, so he ela ion sj`1“ j`1also emains alid o j“h.
We abb e ia e
Dj:“Dmsjpµq:“ IˆJ:IPImsjpA1qand JPImsjpB2qu.
We hen apply he en opy lowe bound in Lemma 2.3, and i s co olla y (2.4), o he
pa i ion 0“ms1ă... ămshămsh`1“ℓmN o 0, . . . , ℓmNu, and he 2-Lipschi z
maps πc:R2ÑRwi h cP ´1,1s:
ż1
´1
Hpπcµ, DℓmN qdνpcq “
h
ÿ
j“1ÿ
QPDj
µpQqż1
´1
HpπcµQ,Dmsj`1´msj|D0qdνpcq
ě ´C0h`
h
ÿ
j“1ÿ
QPDj
µpQqż1
´1
HpπcµQ,Dmp j´sj`1qqdνpcq.(4.65)
Abo e, j´sj`1“ |Jj|. Fo JjPNlow
`, and QPDj, we ecall om (4.58) ha
ż1
´1
HpπcµQ,Dm|Jj|qdνpcq ě log Rm
A1pJjq`ξζ ¨m|Jj|´log 40 ´log C0.
Fo JPPuseless we ha e o se le wi h he es ima e
ż1
0
HpπcµQ,Dm|Jj|qdνpcq ě log Rm
A1pJjq´1
om Lemma 4.60. Plugging hese bounds in o (4.65) (and ede ining C0as C0`1) yields
ż1
´1
Hpπcµ, DℓmN qdνpcq ě ´p40 `C0qh`ÿ
JPP
log Rm
A1pJq`ξζ ÿ
JPNlow
`
|J|
(4.64)
ělog |A1|`ξζ ¨1
2 p1´αq´pα´βq{Γs¨ℓmN ´hp40 `C0q.
Recalling ha |A1| ě δη|A| ě 2p¯α´ηqℓmN , he e exis s cPsp pνqwi h
HℓmN pπcµq ě `¯α`ξζ ¨1
2 p1´αq´pα´βq{Γs´η˘´hp40`C0q
ℓmN
He e hp40 `C0q{pℓmNq ď p40 `C0q{m0ďηby he choice o m0a (4.10), and since we
chose měm0in P oposi ion 4.12. The e o e we ha e es ablished (4.59), and comple ed
he p oo o Theo em 3.28.
38 TUOMAS ORPONEN
5. HAUSDORFF DIMENSION ESTIMATES
The pu pose o his inal sec ion is o educe Theo em 1.6 o Theo em 1.8, and o use
Theo em 1.6 o p o e he Hausdo dimension esul , Co olla y 1.7.
Rema k 5.1.The h eshold γą pα´βq{p1´βq amilia om Theo ems 1.6 and 1.8 plays
no pa icula ole in his sec ion: i we knew ha Theo em 1.8 holds o all γP pτ, 1s o
some pa ame e τ“τpα, βq P p0,1q, hen he a gumen would below would show ha
Theo em 1.6 also holds o γąτ. This is ele an o know i one e en ually manages o
sol e Conjec u e 1.5, and p o es Theo em 1.8 wi h h eshold τpα, βq “ α´β.
5.1. Reducing Theo em 1.6 o Theo em 1.8: ou line. The educ ion om Theo em 1.6
o Theo em 1.8 p oceeds in se e al s ages. Fi s , in Sec ion 5.2, we p o e he ollowing
oy e sion o Theo em 1.6: ins ead o allowing o gene al subse s o he o m GĂ
AˆBwi h |G| ě δǫ|A||B|, his e sion (Theo em 5.3) only ea s subse s o he o m
G“AˆB1wi h |B1| ě δǫ|B|. The conclusion is ha he e exis s cPsp pνqsuch ha
|A`cB1| ě δ´ǫ|A| o all B1ĂBwi h |B1| ě δǫ|B|.
E en he oy e sion, Theo em 5.3, is no p o ed di ec ly: we will pass h ough a oy-
oy e sion, Theo em 5.4, whe e we a e i s allowed o eplace AˆBby a subse o
he o m Aˆ¯
B, and hen he conclusion explained abo e is es ablished o Aˆ¯
Bin
place o AˆB. Fo una ely, he passage be ween he oy and oy- oy e sions can be
accomplished by a o mal exhaus ion a gumen , which I lea ned om He’s pape [17].
The oy- oy e sion is e en ually deduced, in Sec ion 5.4, by a di ec a gumen om
he main Theo em 1.8. This is he hea o he ma e . Ins ead o gi ing de ails he e, I
men ion a key di icul y: his educ ion, and a ious o he s eps o he a gumen would
be simple i we a p io i knew ha
|A`A| « |A|and |B`B| « |B|.(5.2)
(In his heu is ic discussion, I will lea e he meaning o "«" o he eade ’s imagina ion.)
In he case |A| « |B|, ea ed by Bou gain in [5], his is au oma ic: i |A`cB|δ« |A| « |B|
o some cP 1
2,1s, hen (5.2) holds by Plünnecke’s inequali y. Howe e , in ou si ua-
ion Bis ypically much smalle han A, and now he p ope y |A`cB|δ« |A|implies
nei he p ope y in (5.2). Ne e heless, (5.2) is needed, echnically because Lemma 5.16
is useless wi hou (5.2). Roughly speaking, Theo em 5.4 is p o ed by making a coun e
assump ion, and using i o gene a e new se s ¯
A‰Aand ¯
B‰Bwhich sa is y he o igi-
nal hypo heses, and addi ionally (5.2). A some le el, his a gumen is eminiscen o he
p oo o he asymme ic Balog-Szeme édi-Gowe s heo em in [40] (see Theo em 5.38).
Once we ha e he oy e sion, Theo em 5.3, a ou disposal, i emains o deduce
Theo em 1.6 om Theo em 5.3. This s ep is based on he asymme ic Balog-Szeme édi-
Gowe s heo em – unlike he o he s eps. We make a coun e assump ion ha o e e y
cPsp pνq he e exis s a subse GcĂAˆBwi h |G|'|A||B|such ha |πcpGq|δ/|A|. By
he B-S-G heo em, his yields o e e y cPsp pνqsubse s AcĂAand BcĂBsuch ha
|Ac|'|A|,|Bc|'|B|, and |Ac`cBc|δ/|A|. Wi h he help o p obabilis ic a gumen s,
and he Plünnecke-Ruzsa inequali y (Lemma 3.3), his allows us o cons uc a new δ-
sepa a ed se HĂ 0,1swi h |H|/|A|, and a subse CĂsp pνqwi h νpCq'1, such ha
|H`cBc|δ/|H| o all cPC. This iola es he i s oy e sion, Theo em 5.3, applied o
H, B and inally concludes he p oo o Theo em 1.6.
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 39
5.2. A oy e sion. Theo em 1.6 claims he exis ence o cPsp pνqsuch ha |πcpGq| ě
δ´ǫ|A| o all GĂAˆBwi h |G| ě δǫ|A||B|. A oy p oblem is o ind cPsp pνqsuch ha
|A`cB1|δěδ´ǫ|A| o all B1ĂBwi h |B1| ě δǫ|B|. Ins ead o app oaching Theo em 1.6
di ec ly, we will i s sol e his oy p oblem:
Theo em 5.3. Le 0ăβďαă1and κą0. Then, o e e y γP ppα´βq{p1´βq,1s, he e
exis ǫ0, ǫ, δ0P p0,1
2s, depending only on α, β, γ, κ, such ha he ollowing holds. Le δP2´N
wi h δP p0, δ0s, and le A, B Ă pδ¨ZqX 0,1ssa is y he ollowing hypo heses:
(A) |A| ď δ´α.
(B) |B| ě δ´β, and Bsa is ies he ollowing F os man condi ion:
|BXBpx, q| ď κ|B|, δ ď ďδǫ0.
Fu he , le νbe a Bo el p obabili y measu e wi h sp pνq Ă 0,1s, and sa is ying he F os man
condi ion νpBpx, qq ď γ o xPRand 0ă ďδǫ0. Then, he e exis s cPsp pνqsuch ha i
B1ĂBsa is ies |B1| ě δǫ|B|, hen |A`cB1| ě δ´ǫ|A|.
5.3. Reduc ion o a weake oy heo em. E en Theo em 5.3 is ha d o p o e wi h a di ec
assaul . We will i s need o educe i o an e en weake e sion. In he s a emen ,
we use he ollowing no a ion (sligh ly adap ed) om He’s pape [17]. Gi en wo se s
A, B Ă 0,1sXpδ¨Zq, we w i e
EpA|B, ǫq:“ cPR:DB1ĂBsuch ha |B1| ě δǫ|B|and |A`cB1|δăδ´ǫ|A|u.
Theo em 5.4. Le 0ăβďαă1and κ, θ ą0. Then, o e e y γP ppα´βq{p1´βq,1s, he e
exis ǫ0, ǫ, δ0P p0,1
2s, depending only on α, β, γ, κ, such ha he ollowing holds. Le δP2´N
wi h δP p0, δ0s, and le A, B Ă pδ¨ZqX 0,1ssa is y he ollowing hypo heses:
(A) |A| ď δ´α.
(B) |B| ě δ´β, and Bsa is ies he ollowing F os man condi ion:
|BXBpx, q| ď κ|B|, δ ď ďδǫ0.
Fu he , le νbe a Bo el p obabili y measu e wi h sp pνq Ă 0,1s, and sa is ying he F os man
condi ion νpBpx, qq ď γ o xPRand 0ă ďδǫ0. Then, he e exis s a subse B1ĂBsuch
ha νpEpA|B1, ǫqq ď δǫ.
I lea ned his educ ion om he pape o He [17, P oposi ion 25], and his p oo wo ks
he e, up o modi ying he no a ion. The ull de ails a e eco ded below none heless.
P oo o Theo em 5.3 assuming Theo em 5.4.Le α, β, γ, κ be he pa ame e s gi en in Theo-
em 5.3, so ha γą pα´βq{p1´βq. Ou ask is o ind he cons an s ǫ, ǫ0, δ0P p0,1
2s,
depending only on α, β, γ, κ. S a by applying Theo em 5.4 wi h pa ame e s α, ¯
β, γ, ¯κ,
whe e ¯κP p0, κqis a bi a y, and also and ¯
βăβis a bi a y wi h he p ope y ha he
key inequali y
γą pα´¯
βq{p1´¯
βq
emains alid. Le ¯ǫ, ¯ǫ0,¯
δ0P p0,1
2sbe he cons an s gi en by Theo em 5.4, associa ed o
he pa ame e s α, ¯
β, γ, ¯κ. We de ine
ǫ0:“¯ǫ0and ǫ:“min "¯ǫ
2,pκ´¯κq¯ǫ0
4,β´¯
β
2*.(5.5)
40 TUOMAS ORPONEN
We assume ha δ0ď¯
δ0, and he e will be a ew addi ional equi emen s, whe e o
example δďδ0needs o be aken small enough ela i e o he di e ence ¯ǫ´ǫ. I will no
ga he hese equi emen s oge he ; hey will be poin ed ou whe e hey appea .
Le δP2´Nwi h δďδ0, and le A, B, ν be he objec s om Theo em 5.3, sa is ying he
assump ions o ha heo em wi h cons an s α, β, κ, γ, and ǫ0, δ0as abo e. In pa icula ,
|B| ě δ´βand |BXBpx, q| ď κ|B| o xPRand δď ďδǫ0.(5.6)
E iden ly A, B, ν also sa is y he hypo heses o Theo em 5.4 wi h cons an s α, ¯
β, γ, κ{2,
and ¯ǫ0. We now pe o m an "exhaus ion" a gumen o cons uc a ini e sequence o
disjoin subse s B1,...,BNĂBwi h he p ope y
νpEpA|Bj,¯ǫqq ď δ¯ǫ,1ďjďN. (5.7)
Le B1ĂBbe he se gi en ini ially by Theo em 5.4. We hen assume induc i ely ha we
ha e al eady cons uc ed disjoin B1,...,BnĂB o some ně1. The e a e wo op ions:
ˇˇˇBz
n
ď
j“1
Bjˇˇˇăδ2ǫ|B|o ˇˇˇBz
n
ď
j“1
Bjˇˇˇěδ2ǫ|B|.(5.8)
In he o me case, he induc i e cons uc ion e mina es, and we de ine N:“n. In he
la e case, we apply Theo em 5.4 o he objec s A, ν, and B1:“BzŤn
j“1Bj. This is
legi ima e, because |B1| ě δ2ǫ|B| ě δ´β´2ǫěδ´¯
β, and
|B1XBpx, q| (5.6)
ď κ|B| ď δ´2ǫ κ|B1|(5.5)
ď ¯κ|B1|, x PR, δ ď ďδǫ0“δ¯ǫ0.
The e o e A, B1, ν sa is y he hypo heses o Theo em 5.4 wi h cons an s α, ¯
β, ¯κ, γ, ¯ǫ0. Con-
sequen ly, he e exis s a u he subse Bn`1ĂB1“BzŤn
j“1Bjwi h he p ope y
νpEpA|Bn`1,¯ǫqq ď δ¯ǫ. This comple es he induc i e cons uc ion o he sequence
B1,...,BN. The cons uc ion e mina es in ďδ´¯ǫs eps, because he se s Bjsa is y
|Bj| ě δ´¯ǫ. Indeed, since νpEpA|Bj,¯ǫqq ă 1, he e exis s cPsp pνqzEpA|Bj,¯ǫq,
and hen |A||Bj| ě |A`cBj|δěδ´¯ǫ|A|.
When he induc i e p ocedu e e en ually e mina es, we w i e B0:“ŤN
j“1Bj. By
(5.8), we ha e |BzB0| ă δ2ǫ|B|. Now, no e ha he claim o Theo em 5.3 is equi alen o
p o ing ha sp pνqzEpA|B, ǫq ‰ H. We will p o e his by showing ha EpA|B, ǫqhas
small νmeasu e. The i s s ep is o es ablish he ollowing inclusion:
EpA|B, ǫq Ă ď
Jč
jPJ
EpA|Bj,¯ǫq,(5.9)
whe e he index se J uns o e all subse s o 1,...,Nuwi h řjPJ|Bj| ě δǫ|B|{4. The
p oo is nea ly e ba im he same as in [17, P oposi ion 25], bu I eco d he de ails he e
o comple eness. I cPEpA|B, ǫq, hen by de ini ion he e exis s a subse BcĂBwi h
|Bc| ě δǫ|B|and |A`cBc|δăδ´ǫ|A|. Le J:“ 1ďjďN:|BcXBj| ě δ¯ǫ|Bj|u.
Then cPEpA|Bj,¯ǫq o all jPJ, since B1
j:“BcXBjĂBjsa is ies |B1
j| ě δ¯ǫ|Bj|and
|A`cB1
j|δăδ´ǫ|A| ď δ´¯ǫ|A|. This p o es (5.9), once we e i y ha řjPJ|Bj| ě δǫ|B|{4.
To see his, ecall ha |BzB0| ď δ2ǫ|B|. This implies ha Bchas la ge in e sec ion wi h
B0(assuming ha δą0is su icien ly small):
|BcXB0| ě 1
2¨δǫ|B|.
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 47
Rema k 5.37.In o de o deduce Theo em 5.4 o a ixed exponen "κ" om Theo em 5.17,
he a gumen abo e only needed o apply Theo em 5.17 wi h exponen ¯κăκa bi a ily
close o κ(bu ǫÑ0in Theo em 5.4 as ¯κÕκ).
5.5. P oo o he main heo em. In his sec ion, we inally p o e Theo em 1.6 by educ-
ing i o i s oy e sion, Theo em 5.3. We will need he asymme ic Balog-Szeme édi-
Gowe s heo em, see he book o Tao and Vu, [40, Theo em 2.35]. We s a e he esul in
he ollowing sligh ly weake o m ( ollowing Shme kin’s pape [34, Theo em 3.2]):
Theo em 5.38 (Asymme ic Balog-Szeme édi-Gowe s heo em).Gi en ζą0, he e exis s
ξą0such ha he ollowing holds o δP2´Nsmall enough. Le A, B Ă pδ¨ZqX 0,1sbe ini e
se s, and assume ha he e exis cP 1
2,1sand GĂAˆBsa is ying
|G| ě δξ|A||B|and | x`cy :px, yq P Gu|δ“ |πcpGq|δďδ´ξ|A|.(5.39)
Then he e exis subse s A1ĂAand B1ĂBwi h he p ope ies
|A1||B1| ě δζ|A||B|and |A1`cB1|δďδ´ζ|A|.(5.40)
Rema k 5.41.In he e e ences o Theo em 5.38 ci ed abo e, he assump ion |πcpGq|δď
δ´ξ|A|in (5.39) is eplaced by |π1pGq| ď δ´ξ|A|, and he conclusion (5.40) is eplaced by
|A1`B1| ď δ´ζ|A|. Fo cP 1
2,1s, i is easy o see ha he wo a ian s o he heo em a e
o mally equi alen . The de ails a e le o he eade . The idea is o begin by applying
he s anda d e sion o Theo em 5.38 o he se s Bc:“ pcBqδĂδ¨Zand Gc:“ px, pcyqδq:
px, yq P Gu Ă AˆBc, which sa is y |Bc| „ |B|,|Gc| „ |G|, and |π1pGcq| .δ´ξ|A|.
P oo o Theo em 1.6 assuming Theo em 5.3.Le α, β, γ, κ be he cons an s o which we a e
supposed o p o e Theo em 1.6. Thus γą pα´βq{p1´βq. Ou ask is o ind he
cons an s ǫ, ǫ0, δ0P p0,1
2ssuch ha he conclusion o Theo em 1.6 holds. To his end, pick
¯κP p0, κqa bi a ily, and ¯αąα,¯
βăβ, and ¯γăγin such a way ha he key inequali y
¯γą p¯α´¯
βq{p1´¯
βq
pe sis s. This can be done explici ly in such a way ha ¯α, ¯
β, ¯γa e unc ions o α, β, γ:
he e o e, any u u e dependence on ¯α, ¯
β, ¯γwill, in ac , be a dependence on α, β, γ.
Le ¯ǫ, ¯ǫ0,¯
δ0P p0,1
2sbe he cons an s gi en by Theo em 5.3 applied wi h pa ame e s
¯α, ¯
β, ¯γ, ¯κ. We now de ine ǫ, ǫ0, δ0based on ¯ǫ, ¯ǫ0,¯
δ0. Fi s , we se ǫ0:“¯ǫ0. We also ix
δ0P p0,¯
δ0s. The e will be a ew addi ional equi emen s on δ0, depending on α, β, γ, κ
only. These will be cla i ied when hey a ise. We hen inally de e mine he cons an ǫ.
Fi s , we ix a na u al numbe N„1{¯ǫ, su icien ly la ge ha he ollowing holds:
pN´1q´1ă¯ǫ{2.(5.42)
Then, we ix he auxilia y cons an
ζ:“min "¯ǫ
20N,¯ǫ0pκ´¯κq
2N,¯α´α
2NpN`1q,β´¯
β
2N,ǫ0pγ´¯γq
2N*.(5.43)
Now, le ǫ:“ξpζq ą 0be he cons an gi en by Theo em 5.38 applied wi h he cons an
ζą0 om (5.43). This means ha i cP 1
2,1s, and GĂAˆBsa is ies |G| ě δǫ|A||B|
and |πcpGq|δďδ´ǫ|A|, hen he e exis A1ĂAand B1ĂBas in (5.40).
48 TUOMAS ORPONEN
A med wi h hese choices o pa ame e s, we a e p epa ed o p o e Theo em 1.6. Fix
δP2´Nwi h δďδ0, and le A, B, ν be a iple sa is ying he hypo heses o Theo em 1.6
wi h cons an s α, β, γ, κ. To ecap once mo e, |A| ď δα, and |B| ě δ´β, and
|BXBpx, q| ď κ|B|, x PR, δ ď ďδǫ0“δ¯ǫ0.(5.44)
Also, νis a p obabili y measu e on 1
2,1ssa is ying νpBpx, qq ď γ o all δď ďδǫ0.
We claim ha he e exis s cPC:“sp pνqsuch ha whene e GĂAˆBis a subse wi h
|G| ě δǫ|A||B|, hen |πcpGq|δěδ´ǫ|A|.
We make a coun e assump ion: he p ope y abo e ails o e e y cPC. Then, by
he choice ǫ“ξpζq, and Theo em 5.38, o e e y cPC he e exis subse s AcĂAand
BcĂB, o e e y cPC, wi h he p ope ies
|AcˆBc| ě δζ|A||B|and |Ac`cBc|δďδ´ζ|A|.(5.45)
We obse e ha
ż...ż|pAc1ˆBc1qX...XpAcNˆBcNq|dνpc1q¨¨¨dνpcNq ě δNζ |A||B|
by Hölde ’s inequali y. Using pAˆBqXpCˆDq “ pAXCqˆpBXDq, and Chebyshe ’s
inequali y, and νpRq “ 1, i ollows ha he se
Ω :“ pc1,...,cNq P CN:|pAc1X...XAcNqˆpBc1X...XBcNq| ě 1
2δNζ |A||B|u (5.46)
sa is ies
νNpΩq ě 1
2¨δNζ (5.47)
Fo c1,...,cnPC ixed, we de ine
Ωc1¨¨¨cn:“ pcn`1,...,cNq P CN´n:pc1,...,cNq P Ωu.
I ollows easily om Fubini’s heo em ha
νN´npΩc1¨¨¨cnq “ żνN´n´1pΩc1¨¨¨cncqdνpcq(5.48)
o all c1,...,cnPC, and 1ďnďN´2. The same emains ue o n“0, i he le
hand side is in e p e ed as νNpΩq, and c1¨¨¨cnc“c. Equa ion (5.48) also emains alid
o n“N´1i we de ine he no a ion νN´n´1“ν0as ollows:
ν0pΩc1¨¨¨cN´1cq:“1Ωpc1,...,cN´1, cq.(5.49)
We will use his no a ion in he sequel.
Fo pc1,...,cNq P CN ixed, we de ine dec easing sequences o se s Ac1¨¨¨cnuN
n“1and
Bc1¨¨¨cnuN
n“1as ollows:
Ac1¨¨¨cn:“Ac1X...XAcnand Bc1¨¨¨cn:“Bc1X...XBcn,1ďnďN.
The de ini ion o mally makes sense o pc1,...,cNq P CN, bu will only be use ul o
pc1,...,cNq P Ω. Namely, i pc1,...,cNq P Ω, hen i ollows om he de ini ion (5.46) ha
|Ac1¨¨¨cn| ě |Ac1¨¨¨cN| ě 1
2¨δNζ|A|and |Bc1¨¨¨cn| ě 1
2¨δNζ |B|.(5.50)
We now cons uc he se s HnuN
n“1Ăδ¨Z. A he same ime, we will cons uc subse s
C1,...,CNĂC, and poin s cnPCn,1ďnďN, wi h he p ope ies
νN´npΩc1¨¨¨cnq ě 2´n´1δNζ and νpCnq ě 2´n´1δNζ,1ďnďN. (5.51)
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 49
In pa icula , he i s pa o (5.51) wi h n“Nshows ha pc1,...,cNq P Ω, ecall he
no a ion (5.49). To begin wi h, we de ine
C1:“ cPC:νN´1pΩcq ě 2´2δNζ u,
and we choose an a bi a y elemen c1PC1. Since
żνN´1pΩcqdνpcq “ νNpΩq ě 2´1δNζ
by (5.47), and he case n“0o (5.48), we obse e ha νpC1q ě 2´2δNζ by Chebyshe ’s
inequali y. In pa icula C1‰ H. We hen de ine
H1:“ pc1Bc1qδ.
Assume induc i ely ha H1,...,Hnand C1,...,CnĂC, and cjPCj,1ďjďnď
N´1, ha e al eady been cons uc ed, and sa is y (5.51). We hen pick an elemen cn`1P
Cn`1, whe e
Cn`1:“ cPC:νN´n´1pΩc1¨¨¨cncq ě 2´n´2δNζ u,1ďnďN´1.
Fo n“N´1, he no a ion νN´n´1pΩc1¨¨¨cncqshould be in e p e ed as in (5.49), so
CN“ cPC:1Ωpc1,...,cN´1, cq ě 2´N´1δNζ u “ cPC:pc1,...,cN´1, cq P Ωu.
Fo an a bi a y choice cn`1PCn`1, we no e ha he i s pa o (5.51) is sa is ied wi h
index "n`1", simply by he de ini ion o Cn`1.
The se Cn`1also sa is ies he second pa o (5.51) wi h index "n`1", by
2´n´1δNζ (5.51)
ďνN´npΩc1¨¨¨cnq(5.48)
“żνN´n´1pΩc1¨¨¨cncqdνpcq,
and Chebyshe ’s inequali y.
Whe eas c1PC1was chosen a bi a ily, he elemen cn`1PCn`1is chosen in such
a way ha he quan i y |Hn`cn`1Bc1¨¨¨cn`1|δis maximised, among all possible choices
cn`1PCn`1. Fo his choice o cn`1PCn`1, we de ine
Hn`1:“Hn`pcn`1Bc1¨¨¨cn`1qδ.
P oceeding in his manne yields a sequence o se s H1,...,HN, and a dis inguished
sequence pc1,...,cNq P Ω, which we ix o he emainde o he a gumen . We eco d
ha i pc1,¨¨¨, cnq,1ďnďN´1, is an ini ial sequence o pc1,¨¨¨, cNq, hen
|Bc1¨¨¨cnc| ě 1
2δNζ|Bc1¨¨¨cn| ě δ¯ǫ|Bc1¨¨¨cn|, c PCn`1.(5.52)
The second inequali y simply ollows om ou choice o ζa (5.43). To see he i s
inequali y, ecall om he de ini ion o cPCn`1 ha (in pa icula ) Ωc1¨¨¨cnc‰ H (in
he case n“N´1simply pc1,...,cn, cq P Ω). This means ha he e exis s a sequence
pc1
n`2,...,c1
Nq P CN´n´1such ha pc1,...cn, c, c1
n`2,...,c1
Nq P Ω. Consequen ly,
|Bc1¨¨¨cnc| ě |Bc1X¨¨¨BcnXBcXBc1
n`2X¨¨¨Bc1
N| ě 1
2δNζ |B| ě 1
2δNζ|Bc1¨¨¨cn|
by he de ini ion o Ω, see (5.46).
No e ha HnĂ pδ¨Zq X 0, ns o all 1ďnďNby a s aigh o wa d induc ion, so
|Hn| ď 2Nδ´1. The e o e, by he pigeonhole p inciple, he e exis s an nP 1,...,N ´1u
such ha
|Hn`1| ď p2Nδ´1q1{pN´1q|Hn| ď 4δ´1{pN´1q|Hn|.(5.53)
50 TUOMAS ORPONEN
We now conside he objec s
¯
A:“Hn,¯
B:“Bc1¨¨¨cn,and ¯ν:“νpCn`1q´1ν|Cn`1.(5.54)
We will show in a momen hese objec s sa is y he hypo heses o Theo em 5.3 wi h con-
s an s ¯α, ¯
β, ¯κ, ¯γ, and ¯ǫ0. Fi s , howe e , we conclude he p oo o Theo em 1.6, aking
his o g an ed. By Theo em 5.3, he e exis s ¯cPCn`1(a se o ull ¯νmeasu e) such ha
whene e B1Ă¯
Bis a se o ca dinali y |B1| ě δ¯ǫ|B|, we ha e
|Hn`¯cB1|δ“ | ¯
A`¯cB1|δěδ´¯ǫ|¯
A| “ δ´¯ǫ|Hn|.(5.55)
(To be accu a e, Theo em 5.3 only claims his o some ¯cPsp p¯νq, bu he p oo showed,
see (5.10), ha ac ually he se o non-admissible cPsp p¯νqha e measu e s ic ly smalle
han 1, so we can pick cPCn`1.) Howe e , o e e y cPCn`1, he se B1:“Bc1¨¨¨cncĂ
Bc1¨¨¨cn“¯
Bsa is ies
|B1|(5.52)
ěδ¯ǫ|¯
B|and |Hn`cB1|δ.|Hn`1|(5.53)
ď4δ´1{pN´1q|Hn|(5.42)
ďδ´¯ǫ{2|Hn|.(5.56)
The inequali y |Hn`cB1|δ.|Hn`1| ollows om he ac ha whene e cPCn`1, he
se Hn` pcB1qδ“Hn` pcBc1¨¨¨cncqδis a compe i o in he de ini ion o Hn`1. Wi h he
choice c“¯cPCn`1, he inequali ies (5.55)-(5.56) a e mu ually incompa ible o δą0
small enough, depending on ¯ǫ“¯ǫpα, β, γ, κq ą 0. A con adic ion has been eached.
I emains o check ha ha he objec s in (5.53) sa is y he hypo heses o Theo em 5.3
wi h cons an s ¯α, ¯
β, κ{2,¯γ, and ¯ǫ0. Mo e p ecisely:
(a) |¯
A| ď δ´¯α,
(b) |¯
B| ě δ´¯
β, and ¯
Bsa is ies a F os man condi ion wi h exponen ¯κ, o P δ, δ¯ǫ0s,
(c) ¯νsa is ies a F os man condi ion wi h exponen ¯γ.
We i s use he Plünnecke-Ruzsa inequali y o es ablish (a), assuming ha δą0is su -
icien ly small in e ms o N, ¯α. I is clea by induc ion ha Hncan be w i en as a sum
o nďNse s o he o m pcmBc1¨¨¨cmqδ, o some 1ďmďn. No ing ha Ac1¨¨¨cnĂAcm,
each o hese se s indi idually sa is ies
|Ac1¨¨¨cn`pcmBc1¨¨¨cmqδ|.|Acm`cmBcm|δ
(5.45)
ďδ´ζ|A|(5.50)
ď2δ´pN`1qζ|Ac1¨¨¨cn|.
We may he e o e in e ha
|Hn|.Nδ´NpN`1qζ|A| ď δ´NpN`1qζ´α.
om he Plünnecke-Ruzsa inequali y, Lemma 3.3, applied wi h Ac1¨¨¨cnin place o A(and
inally also using |Ac1¨¨¨cn| ď |A| ď δ´α, see abo e (5.44)). This inequali y implies |Hn| ď
δ´¯α o small enough δą0, ecalling ou choice o ζa (5.43).
We mo e o (b). Recall om (5.44) ha he se Bsa is ies he assump ions o Theo em
1.6 wi h cons an s ǫ0, κ ą0:
|BXBpx, q| ď κ|B|, x PR, δ ď ďδǫ0“δ¯ǫ0.
Since Bc1¨¨¨cnĂB, and |Bc1¨¨¨cn| ě 1
2δNζ |B|by (5.50), we deduce ha Bc1¨¨¨cnsa is ies a
F os man condi ion wi h exponen ¯κ:
|Bc1¨¨¨cnXBpx, q| ď 2δ´Nζ κ|Bc1¨¨¨cn| ď ¯κ|Bc1¨¨¨cn|, x PR, δ ď ďδ¯ǫ0.
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 51
The inal inequali y uses ou choice o ζin (5.43), and also assumes ha δą0is su i-
cien ly small, depending on ¯ǫ0, κ. Mo eo e , since |B| ě δ´βby assump ion, we ha e
|Bc1¨¨¨cn| ě 1
2δNζ |B|(5.43)
ěδ´¯
β.
Le us inally check (c), namely ha he p obabili y measu e ¯ν“νpCn`1q´1¨ν|Cn`1sa is-
ies a F os man condi ion wi h exponen ¯γ. Indeed, ecalling om (5.51) ha νpCn`1q ě
2´n´2δNζ , we ha e
¯νpBpx, qq ď 2n`2δ´NζνpBpx, qq ď 2N`2δ´Nζ ¨ γ, x PR, δ ď ďδ¯ǫ0.
Since γďδǫ0pγ´¯γq ¯γ o ďδǫ0, by ou choice o ζin (5.43), he igh hand side is
bounded om abo e by ¯γ o all δą0small enough, depending on N, γ, ¯γ(all o which
only depend on α, β, γ, κ). We ha e now e i ied ha he objec s ¯
A, ¯
B, ¯ν om (5.54)
sa is y he hypo heses o Theo em 5.3. This concludes he p oo o Theo em 1.6.
Rema k 5.57.Once again, in o de o deduce Theo em 1.6 o a ixed exponen "κ" om
Theo em 5.3, we only needed o apply Theo em 5.3 wi h a ixed exponen ¯κP p0, κq,
as close o κas we desi e. Combining his wi h he p e ious simila Rema ks 5.11-5.37,
we ob ain he conclusion alluded o in Rema k 1.9: o deduce Theo em 1.6 o a ixed
exponen "κ" om Theo em 1.8, we only needed o apply Theo em 1.8 o ¯κP p0, κq
a bi a ily close o κ.
5.6. P oo o Co olla y 1.7.I close he pape by eco ding he (s anda d pigeonholing)
p oo o Co olla y 1.7, whose s a emen is ecalled he e:
Co olla y 5.58. Le 0ăβďαă1and κą0. Then, he e exis s η“ηpα, β, κq ą 0such ha
i A, B ĂRa e Bo el se s wi h dimHA“α,dimHB“β, hen
dimH cPR: dimHpA`cBq ď α`ηu ď α´β
1´β`κ.
P oo . I is easy o educe o he case whe e A, B a e compac , A, B Ă 0,1s, and HαpAq ą
0and HβpBq ą 0. In his case, one may use F os man’s lemma [23, Theo em 8.8] o
ind Bo el p obabili y measu es µA, µBwi h sp pµAq Ă A,sp pµBq Ă B, and sa is ying
µApBpx, qq ď CA αand µBpBpx, qq ď CB β o all balls Bpx, q Ă R. I ηą0is small
enough, we will show ha dimHEď pα´βq{p1´βq`κ, whe e
E:“Eη:“ cP 1
2,1s: dimHpA`cBq ă α`ηu.
I is easy o show (by escaling conside a ions) ha his implies Co olla y 1.7, whe e
1
2,1sis eplaced by R. I is well-known ha he se EĂ 1
2,1sis Bo el. Consequen ly,
i he inequali y ails, one may use F os man’s lemma again o ind a Bo el p obabili y
measu e ν, suppo ed on E, sa is ying νpBpx, qq ď Cν γ o all xPRand ą0, whe e
γě pα´βq{p1´βq`κ.
Fo u u e e e ence, we ix some pa ame e s ¯αąα,¯
βăβ, and ¯γăγsuch ha he
inequali y
¯γą p¯α´¯
βq{p1´¯
βq(5.59)
s ill holds. We hen le ¯ǫ, ¯ǫ0,¯
δ0ą0be he cons an s p o ided by Theo em 1.6 applied
wi h pa ame e s ¯α, ¯
β, κ “¯
β, ¯γ. We pick ηą0in he de ini ion o Eso small ha
ηămin ¯ǫ, ¯α´αu.(5.60)
52 TUOMAS ORPONEN
Fix cPsp pνq Ă E, so dimHpA`cBq ă α`η. This means ha o a gi en ixed
h eshold δ0:“2´j0P2´N( he equi emen s will depend on α, β, γ, CA, CB, Cν), one
may ind a coun able co e Ico A`cB, consis ing o disjoin dyadic in e als o leng h
ℓpIq ď δ0, such ha
ÿ
IPIc
ℓpIqα`ηď1.(5.61)
Below, we will o en w i e ha some hing holds " o small enough δą0": his will
always mean "assuming ha he uppe bound δ0 o δhas been chosen su icien ly small,
depending on he pa ame e s α, β, γ, CA, CB, Cν. In pa icula , we will ake δ0ď¯
δ0.
The " ubes" Tc:“ π´1
cpIquIPIcco e AˆBĄsp pµAˆµBq, so
żEÿ
TPTcpµAˆµBqpTqdνpcq “ 1.
Recall ha δ0“2´j0, and le Ij
c:“ IPIc:ℓpIq “ 2´ju o jěj0. W i e also Tj
c:“
π´1
cpIquIPIj
c. Since Tc“Ťjěj0Tj
c, he e exis s jěj0such ha
żEÿ
TPTj
c
pµAˆµBqpTqdνpcq&j´2.
W i e δ:“2´j o his index j. Acco ding o he es ima e abo e, he e exis s a subse
E1
δĂEo measu e νpE1
δq&j´2“log2p1{δq´2such ha o each cPE1
δ, he ubes TPTj
c
co e a subse GcĂsp pµAˆµBqo measu e pµAˆµBqpGcq&log2p1{δq´2. In pa icula ,
we eco d ha
|πcpGcq|δď |Tj
c| ď δ´α´η, c PE1
δ,(5.62)
by (5.61). Fo he emainde o his a gumen , we use he no a ion /g o abb e ia e an
inequali y o he o m ďClog2p1{δqCg o some cons an Cą0, which may depend
on he F os man cons an s α, β, γ, CA, CB, Cν. In pa icula , j´2“log2p1{δq´2'1.
Fo xPR, le Iδpxq P Dδbe he unique dyadic in e al o leng h δwi h xPIδpxq. We
now spli he se Aas ollows:
A“ď
ρP2´N
Apρq:“ xPA:ρďµApIδpxqq ă 2ρu.
We de ine he se s Bpρq Ă Bsimila ly. Since µApIδpxqq ď CAδαand µBpIδpyqq ď CBδβ,
we see ha Apρq ‰ H implies ρďCAδα, and Bpρq ‰ H implies ρďCβδβ. We also
no e ha Apρqcan be exp essed as he in e sec ion o Awi h ce ain dyadic in e als
Apρq Ă Dδ. The same is ue o Bpρq, o ce ain dyadic in e als Bpρq Ă Dδ.
Le µApρqbe he es ic ion o µA o he in e als Apρq, and simila ly le µBpρqbe he
es ic ion o µB o he in e als in Bpρq. Then
ÿ
ρ1ÿ
ρ2żE1
δpµApρ1qˆµBpρ2qqpGcq « 1,(5.63)
so i ollows om he pigeonhole p inciple ha
żE1
δpµApρAqˆµBpρAqqpGcq « 1
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 53
o some ixed choices ρAďCAδαand ρBďCBδβ(no ing ha alues ρ1, ρ2ďδ2canno
con ibu e subs an ially o he sum in (5.63)). In pa icula , he e exis s a u he subse
EδĂE1
δwi h he p ope y pµApρAqˆµBpρBqqpGcq « 1 o all cPEδ. We now abb e ia e
¯µA:“µApρAqand ¯µB:“µBpρBq,
so }¯µA} « 1« }¯µB}. The measu e ¯µAis suppo ed on he closu e o he in e als in
ApρAq, and ¯µBis suppo ed on he closu e o he in e als in BpρBq. Le
Aδ:“ pδ¨ZqXpYApρAqq and Bδ:“ pδ¨ZqXpYBpρBqq.
We obse e ha
ρA¨|Aδ| „ }µA} « 1ùñ ρA« |Aδ|´1,(5.64)
and simila ly ρB« |Bδ|´1. Since ρAďCAδα, we eco d ha
|Aδ| « ρ´1
A'δ´α.(5.65)
We nex claim ha , somewha con e sely, |Aδ| ď δ´¯αi δą0is su icien ly small. To see
his, ix an a bi a y cPEδ. Since p¯µAˆ¯µBqpGcq « 1, he e exis s bPsp p¯µBqsuch ha
¯µApGcpbqq « 1,whe e Gcpbq “ xPsp p¯µAq:px, bq P Gcu.
Now, i Gcpbq:“ IPApρAq:Gcpbq X I‰ Hu, we see ha ¯µApIq „ ρA o all IPGcpbq,
and ¯µApYGcpbqq ě ¯µApGcpbqq « 1. Mo eo e , we obse e ha |Gcpbq|δ.|πcpGcq|δ, since
πcpGcq Ą Gcpbq`bc. Pu ing hese obse a ions oge he ,
|Aδ|(5.64)
«ρ´1
A/ρ´1
A¨¯µApYGcpbqq .|Gcpbq|δ.|πcpGcq|δ
(5.62)
ďδ´α´η.(5.66)
Since α`ηă¯αby (5.60), he inequali y |Aδ| ď δ´¯αholds o δą0su icien ly small.
Nex , since ρBďCBδβ, we eco d ha
|Bδ| « ρ´1
B'δ´βùñ |Bδ| ě δ¯
β,(5.67)
whe e he implica ion holds i δą0is su icien ly small. Mo eo e , o xPRand ěδ,
we no e ha e e y poin yPBδXBpx, qis con ained in an in e al Iypδq P BpρBqwi h
µBpIypδqq ě ρB. Since Iypδq Ă Bpx, 2 q, we deduce ha
|BδXBpx, q| ď ρ´1
B¨µBpBpx, 2 qq ď ρ´1
B¨CBp2 qβ/ β|Bδ|.(5.68)
In pa icula , o he pa ame e ¯ǫ0ą0 ixed below (5.59), we ha e |BδXBpx, q| ď ¯
β|Bδ|
o δď ďδ¯ǫ0, p o ided ha δą0is small enough.
Finally, he measu e νδ:“νpEδq´1¨ν|Eδsa is ies
νδpBpx, qq /νpBpx, qq ď Cν γ, ą0,(5.69)
so he inequali y νδpBpx, qq ď ´¯γholds o all ďδ¯ǫ0, p o ided ha δą0is small
enough. The es ima es (5.66)-(5.69), and (5.59), imply ha he iple Aδ, Bδ, νδsa is ies all
he hypo heses o Theo em 1.6 wi h cons an s ¯α, ¯
β, κ “¯
β, ¯γ, and ¯ǫ0. Consequen ly, he e
exis s cPEδĂE1
δ(a se o ull νδmeasu e) such ha
|πcpGq|δěδ´¯ǫ|Aδ|
(5.65)
'δ´α´¯ǫ(5.70)
o all subse s GĂAδˆBδo ca dinali y |G| ě δ¯ǫ|A||B|. We a gue ha his con adic s
(5.62). The only issue is ha se GcĂsp pµAˆµBqis no exac ly a subse o AδˆBδ. To
ix his, ecall ha ne e heless p¯µAˆ¯µBqpGcq « 1. Le
Gc:“ IˆJPApρAqˆBpρBq:pIˆJqXGc‰ Hu.
54 TUOMAS ORPONEN
Then Gcis a co e o Gc, and p¯µAˆ¯µBqpQq „ ρAρB« |Aδ|´1|Bδ|´1 o all Q“IˆJPGc.
Consequen ly,
|Gc|&pρAρBq´1¨p¯µAˆ¯µBqpGcq « |Aδ||Bδ|.
Now, le Gc,δ Ă pAδˆBδqXGcp2δqbe subse o ca dinali y |Gc,δ|'|Aδ||Bδ|. In pa icula
|Gc,δ| ě δ¯ǫ|Aδ||Bδ| o δą0small enough. The e o e he es ima e (5.70) holds o G“
Gc,δ. On he o he hand, since Gc,δ ĂGcp2δq, we ha e
|πcpGc,δq|δ.|πcpGcq|δďδ´α´η
by (5.62). Since we chose ηă¯ǫin (5.60), his es ima e is no compa ible wi h (5.70). A
con adic ion has been eached, and he p oo o Co olla y 1.7 is comple e.
REFERENCES
[1] Y es Benois and Nicolas de Saxcé. A spec al gap heo em in simple Lie g oups. In en . Ma h.,
205(2):337–361, 2016.
[2] J. Bou gain. On he E dös-Volkmann and Ka z-Tao ing conjec u es. Geom. Func . Anal., 13(2):334–365,
2003.
[3] J. Bou gain and A. Gambu d. A spec al gap heo em in SUpdq.J. Eu . Ma h. Soc. (JEMS), 14(5):1455–
1511, 2012.
[4] Jean Bou gain. Mul ilinea exponen ial sums in p ime ields unde op imal en opy condi ion on he
sou ces. Geom. Func . Anal., 18(5):1477–1502, 2009.
[5] Jean Bou gain. The disc e ized sum-p oduc and p ojec ion heo ems. J. Anal. Ma h., 112:193–236, 2010.
[6] Jean Bou gain and Alex Gambu d. On he spec al gap o ini ely-gene a ed subg oups o SUp2q.In-
en . Ma h., 171(1):83–121, 2008.
[7] Damian D ˛ab owski, Tuomas O ponen, and Michele Villa. In eg abili y o o hogonal p ojec ions, and
applica ions o Fu s enbe g se s. Ad . Ma h., 407:Pape No. 108567, 34, 2022.
[8] P. E d˝os and E. Szeme édi. On sums and p oduc s o in ege s. In S udies in pu e ma hema ics, pages
213–218. Bi khäuse , Basel, 1983.
[9] K. J. Falcone . Hausdo dimension and he excep ional se o p ojec ions. Ma hema ika, 29(1):109–115,
1982.
[10] Yuqiu Fu, Shengwen Gan, and Ke in Ren. An incidence es ima e and a Fu s enbe g ype es ima e o
ubes in R2.J. Fou ie Anal. Appl., 28(4):Pape No. 59, 28, 2022.
[11] M. Z. Ga ae . An explici sum-p oduc es ima e in Fp.In . Ma h. Res. No . IMRN, (11):A . ID nm035,
11, 2007.
[12] A. A. Glibichuk and S. V. Konyagin. Addi i e p ope ies o p oduc se s in ields o p ime o de . In Ad-
di i e combina o ics, olume 43 o CRM P oc. Lec u e No es, pages 279–286. Ame . Ma h. Soc., P o idence,
RI, 2007.
[13] La y Gu h, Ne s Hawk Ka z, and Joshua Zahl. On he disc e ized sum-p oduc p oblem. In . Ma h.
Res. No . IMRN, (13):9769–9785, 2021.
[14] La y Gu h, Noam Solomon, and Hong Wang. Incidence es ima es o well spaced ubes. Geom. Func .
Anal., 29(6):1844–1863, 2019.
[15] Ka alin Gya ma i, Má é Ma olcsi, and Im e Z. Ruzsa. Plünnecke’s inequali y o di e en summands.
In Building b idges, olume 19 o Bolyai Soc. Ma h. S ud., pages 309–320. Sp inge , Be lin, 2008.
[16] Weikun He. Disc e ized sum-p oduc es ima es in ma ix algeb as. J. Anal. Ma h., 139(2):637–676, 2019.
[17] Weikun He. O hogonal p ojec ions o disc e ized se s. J. F ac al Geom., 7(3):271–317, 2020.
[18] Weikun He and Nicolas de Saxcé. Sum-p oduc o eal Lie g oups. J. Eu . Ma h. Soc. (JEMS), 23(6):2127–
2151, 2021.
[19] Michael Hochman. On sel -simila se s wi h o e laps and in e se heo ems o en opy. Ann. o Ma h.
(2), 180(2):773–822, 2014.
[20] Robe Kau man. On Hausdo dimension o p ojec ions. Ma hema ika, 15:153–155, 1968.
[21] Jialun Li. Disc e ized Sum-p oduc and Fou ie decay in Rn.J. Anal. Ma h., 143(2):763–800, 2021.
[22] J. M. Ma s and. Some undamen al geome ical p ope ies o plane se s o ac ional dimensions. P oc.
London Ma h. Soc. (3), 4:257–302, 1954.
ON THE DISCRETISED ABC SUM-PRODUCT PROBLEM 55
[23] P. Ma ila. Geome y o se s and measu es in Euclidean spaces. F ac als and ec i iabili y. 1s pape back ed.
Camb idge: Camb idge Uni e si y P ess, 1s pape back ed. edi ion, 1999.
[24] Ali Mohammadi and Sophie S e ens. A aining he exponen 5/4 o he sum-p oduc p oblem in ini e
ields. In . Ma h. Res. No . IMRN, (4):3516–3532, 2023.
[25] Daniel M. Obe lin. Some oy Fu s enbe g se s and p ojec ions o he ou -co ne Can o se . P oc. Ame .
Ma h. Soc., 142(4):1209–1215, 2014.
[26] Tuomas O ponen. On he dis ance se s o Ahl o s-Da id egula se s. Ad . Ma h., 307:1029–1045, 2017.
[27] Tuomas O ponen. On a i hme ic sums o Ahl o s- egula se s. Geom. Func . Anal., 32(1):81–134, 2022.
[28] Tuomas O ponen and Pablo Shme kin. On he Hausdo dimension o Fu s enbe g se s and o hogonal
p ojec ions in he plane. Duke Ma h. J. ( o appea ).
[29] Tuomas O ponen and Lau a Venie i. A no e on expansion in p ime ields. a Xi e-p in s, page
a Xi :1801.09591, Janua y 2018.
[30] Yu al Pe es and Wilhelm Schlag. Smoo hness o p ojec ions, Be noulli con olu ions, and he dimension
o excep ions. Duke Ma h. J., 102(2):193–251, 2000.
[31] O i E. Raz and Joshua Zahl. On he dimension o excep ional pa ame e s o nonlinea p ojec ions,
and he disc e ized Elekes-Rónyai heo em. Geom. Func . Anal. ( o appea ).
[32] Misha Rudne and Sophie S e ens. An upda e on he sum-p oduc p oblem. Ma h. P oc. Camb idge
Philos. Soc., 173(2):411–430, 2022.
[33] Im e Z. Ruzsa. An applica ion o g aph heo y o addi i e numbe heo y. Sci. Se . A Ma h. Sci. (N.S.),
3:97–109, 1989.
[34] Pablo Shme kin. On Fu s enbe g’s in e sec ion conjec u e, sel -simila measu es, and he Lqno ms o
con olu ions. Ann. o Ma h. (2), 189(2):319–391, 2019.
[35] Pablo Shme kin. On he Hausdo dimension o pinned dis ance se s. Is ael J. Ma h., 230(2):949–972,
2019.
[36] Pablo Shme kin. A nonlinea e sion o bou gain’s p ojec ion heo em. (J. Eu . Ma h. Soc. o appea ),
2020.
[37] Pablo Shme kin and Hong Wang. On he dis ance se s spanned by se s o dimension d{2in Rd.a Xi
e-p in s, page a Xi :2112.09044, Decembe 2021.
[38] Sophie S e ens and F ank de Zeeuw. An imp o ed poin -line incidence bound o e a bi a y ields.
Bull. Lond. Ma h. Soc., 49(5):842–858, 2017.
[39] End e Szeme édi and William T. T o e , J . Ex emal p oblems in disc e e geome y. Combina o ica, 3(3-
4):381–392, 1983.
[40] Te ence Tao and Van Vu. Addi i e combina o ics, olume 105 o Camb idge S udies in Ad anced Ma hema -
ics. Camb idge Uni e si y P ess, Camb idge, 2006.
DEPARTMENT OF MATHEMATICS AND STATISTICS, UNIVERSITY OF JYVÄSKYLÄ, P.O. BOX 35 (MAD),
FI-40014 UNIVERSITY OF JYVÄSKYLÄ, FINLAND
Email add ess:[email p o ec ed]