On the geometry of a class of invariant measures and a problem of Aldous

800andaproblemofAldous

2 guTimAustin

A 61Abstract

]RInhissurvey[4]ofnotionsofexchangeability,Aldousintroducedaformofex-Pchangeabilitycorrespondingtothesymmetriesoftheinfinitediscretecube,andasked.hwhethertheseexchangeableprobabilitymeasuresenjoyarepresentationtheoremsim-tailartothoseforexchangeablesequences[11],arrays[12,13,1,2]andset-indexedmfamilies[15].Inthisnotewetoprovethat,whereastheknownrepresentationtheo-[ remsfordifferentclassesofpartiallyexchangeableprobabilitymeasureimplythatthe 1compactconvexsetofsuchmeasuresisaBauersimplex(thatis,itssubsetofextremevpointsisclosed),inthecaseofcube-exchangeabilityitisacopyofthePoulsensim-86plex(inwhichtheextremepointsaredense).Thisfollowsfromtheargumentsused2byGlasnerandWeiss’fortheircharacterizationin[9]ofproperty(T)intermsofthe2geometryofthesimplexofinvariantmeasuresforassociatedgeneralizedBernoulli.8actions.

08TheemergenceofthisPoulsensimplexsuggeststhat,ifarepresentationtheoremfortheseprocessesisavailableatall,itmusttakeaverydifferentformfromthecase:0vofset-indexedexchangeablefamilies.

iXraContents

1Introduction

2Theformofpreviousrepresentationtheoremsforexchangeablemeasures3Bauersimplicesfromexchangeability

3.1TheBauerpropertyfromrepresentability.................3.2TheBauerpropertyintheparticularcontextofhypergraphexchangeability4ThePoulsenpropertyforcube-exchangeablemeasures

1

246789

5Somefurtherquestions

5.1Furtheranalysisofcube-exchangeablemeasures.........5.2Thegeometryofsubsimplicesandrelationstopropertytesting.5.3Affinetransformationsoftheinfinite-dimensionaldiscretecube.5.4ThePoulsenpropertyforotherexchangeabilitycontexts....5.5Cube-exchangeabilityforfiner-grainedcubes..........

.........................

121214171818

1Introduction

SupposethatKisastandardBorelspacewithσ-algebraΣK,thatTisacountablyin-finitesetandΓagroupofpermutationsofTandthatµisaprobabilitymeasureonthe

T

(standardBorel)productmeasurablespace(KT,Σ⊗K).LetusalsoalwaysassumethatΓhasonlyinfiniteorbitsinT.ThenfollowingAldous[4]weshallwritethatµis(T,Γ)-exchangeableifitisinvariantunderthe(contravariant)coordinate-permutingactionτofΓonKTgivenby󰀁󰀂γ

τ(ωt)t∈T:=(ωγ(t))t∈T,whichisclearlymeasurableandinvertible.WewritePrΓKTforthesetofallsuchex-changeableprobabilitymeasures.Weshallsometimesrefertotheindex-setactionΓ󰀆Tasanexchangeabilitycontext.

Theprototypicalexamplesofexchangeabilityarearguablythoseofhypergraphexchange-󰀁S󰀂

ability,forwhichT=k,thesetofallk-subsetsofacountablyinfinite‘vertexset’S,andΓ=Sym0(S),thegroupofallfinitely-supportedpermutationsofSactingonTbyvertex-permutations.Inthiscasewecaninterpretµasthelawofarandom‘colouring’ofthecompletek-uniformhypergraphonSbypointsfromthespaceKof‘colours’.Inthesimplestcasek=1(soT=S),theprecisestructureofallpossiblehypergraph-exchangeablemeasuresfollowsfromclassicaltheoremsofdeFinettiandHewitt&Sav-age(see,forexample,[11]).Morerecently,thecaseofmoregeneralkwasstudiedbyHoover[12,13],Aldous[1,2,4]andKallenberg[15],alongwithanumberoffurtherextensionsthatarestillcloselyrelatedtothishypergraph-colouringsetting,leadingtoamoreelaborateconceptionof‘exchangeabilitytheory’.Itturnsoutthatinthesecontextstootheexchangeableprobabilitymeasuresadmitamore-or-lesscompletestructuralde-scription,albeitinvolvingincreasinglycomplicatedingredientsaskincreases:theycanallberepresentedasimagesofcertainotherexchangeableprocesseswhoselawstakeaparticularsimpleform.Wereferthereaderto[6]forarecentsurveyoftheseresultsandtheirrelationstovariousquestionsingraphandhypergraphtheory,andtothesurvey[4]ofAldousforageneralintroductiontoabroaderrangeofexchangeabilitycontextsandto

2

therecentbookofKallenberg[17]forthemodernstateofthetheory.

Wewillnotrecountthedetailsoftheserepresentationtheoremshere.Rather,ourinterestliesinadifferentexchangeabilitycontext,proposedbyAldousasapossibleobjectoffurtherstudyinSection16of[4]:thatofcube-exchangeability.LetF2={0,1}bethefieldoftwoelements,andinthed-dimensionalvectorspaceFd2overF2writee1,e2,...,ed

⊕N

forthestandardbasis.NowtakeTtobethesetF2ofallstringsof0sand1swithonlyfinitelymanyofthelatter,andletΓbethegroupofpermutationsofTgeneratedbyfinitely-supportedpermutationsoftheunderlyingcopyofNtogetherwithall‘bit-flips’:

⊕NN

σi:F2→F⊕2:x→x+ei.Inthiscontext,givenanystandardBorelspaceKweshallcallaprobabilitymeasureµonKTcube-exchangeableifitisinvariantunderthecoordinate-permutingactionoftheabovegroupΓ.Notefollows:Tmaybewrittenasthe󰀍thatwemaydescribethisgroupasn

increasingunionn≥1TnofthediscretecubesTn:=F2,andnow(bearinginmindourrestrictiontofinitely-supportedpermutationsofN)everymemberg∈ΓactuallymapsTnontoitselfforallsufficientlylargen.ItiseasytoseethatinthiscaseapermutationofTnisinducedbyamemberofΓifandonlyifitisanisometryofTnwhenthislatterisidentifiedwiththen-dimensionalHammingcube{0,1}n.ForthisreasonweshallrefertoΓasthegroupofisometriesoftheinfinite-dimensionaldiscretecubeanddenoteitby

N

IsomF⊕2.Notethat,asinthesettingofhypergraph-exchangeability,theactinggroupΓislocallyfinite(thatis,anyfinitecollectionofitselementsgeneratesafinitesubgroup);butunlikeinthatsettingmostelementsofthegroup(tobeprecise,allthatinvolveanontrivialtranslation)domoveinfinitelymanypointsofT.

Inviewofthesuccessofthebasictheoryofhypergraph-exchangeability,Aldousaskedin[4]whetherasimilarlyprecisestructuraldescriptionisavailablefortheclassofcube-exchangeableprobabilitymeasures.Inthisnotewewillprovidesomeevidencetosuggestthatsuchastructuraldescriptionmaynotbeavailableinthiscontext—atleastnotintheveryexplicitformfamiliarfromthehypergraphsetting—inthefollowing‘soft’sense.First,wenotethat,providedΓisamenable(asitcertainlyisinourexamples),thebasicrepresentationtheoremsforhypergraphexchangeablelawsfallintoacertainquitegeneralpattern,andthatthispatternhas,inparticular,theconsequencethatforacompactmetricKthesetofallextremepoints(thatis,ergodicmembers)ofPrΓKTformsaclosedsub-groupofthiscompactconvexsetinthevaguetopology;thatis,thisconvexsetisaBauersimplex.Ontheotherhand,wewillshowthatprovidedKisnotasingleton,thissetPrΓKTinthecaseofcube-exchangeabilityhastheverydifferentpropertyofbeingacopyofthePoulsensimplex:itsextremepointsformavaguelydensesubset.Thissuggeststhatanyrepresentationtheoremdescribingthisset,ifoneisavailable,musttakearatherdifferentformfromtheearlierset-indexedexamples.

3

Remarkonnotation

Ourbasiccombinatorialandmeasure-theoreticnotationiscompletelystandard.If(X,ρ)isametricspace,x,y∈Xandε>0,weshallsometimeswritex≈εyinplaceofρ(x,y)<εwhentheparticularmetricρisunderstood.Acknowledgements

MythanksgotoTerenceTaoandYehudaShalomforhelpfuldiscussions.

2Theformofpreviousrepresentationtheoremsforex-changeablemeasures

Inthissectionweintroduceageneraltemplateforakindofrepresentationtheoremforexchangeablelaws,whichinparticularcharacterizesthebasicrepresentationtheoremsfortheclusterofvariationsonhypergraph-exchangeability.

Thesetheoremsallfocusonrepresentinganarbitrary(T,Γ)-exchangeableprocessasanimage(inasuitablesense)ofanotherexchangeableprocess(possiblywithadifferentindexset)forwhichthedifferentrandomvariablesareallmutuallyindependent.Definition2.1(Ingredients).LetΓ󰀆TbeanexchangeabilitycontextandKafixedcompactmetricspace.Byalistofrepresentationdataweunderstand:

•asequenceofauxiliaryindexsetsT1,T2,...eachendowedwithsomeactionΓ󰀆Tithathasonlyinfiniteorbits;

󰀁Ti󰀂

•adisjointsequenceofdependencymapsφi:T→<∞thatareΓ-covariant,inthatφi(γ(t))=γ(φi(t));•andafamilyofprobabilitykernels

κt:[0,1]×[0,1]φ1(t)×[0,1]φ2(t)×···󰀃K

γ

thatisΓ-covariant,inthatκγ(t)=κt◦(id[0,1]×τ1×···).

Giveningredientsasabove,wedenotebyκ(T)thekernel[0,1]×[0,1]T1×[0,1]T2×···󰀃KTgivenby󰀇

(T)

κ(x0,x1,...,·)=κt(x0,x1|φ1(t),...,·).

t∈T

4

Oftheconditionsonthedataintroducedabove,perhapstheleastintuitiveisthattheactionsΓ󰀆Timaynothavefiniteorbits(althoughitcertainlyholdsinthecaseofhypergraphexchangeability);weshalllaterneedtoplaythisoffagainstthefinitenessofthesetsφi(t),anditdoesholdforthecaseofhypergraph-exchangeability.

NowandhenceforthwewilldenotebyµLLebesguemeasureontheunitinterval[0,1],

T1⊗T2⊗···T1T2

andbytheshorthandµ∗⊗theproductmeasureµL⊗µ⊗⊗µ⊗⊗···.LLLDefinition2.2(Representability).GivenanexchangeabilitycontextΓ󰀆TandacompactmetricspaceK,weshallsaythata(T,Γ)-exchangeablelawµ∈PrKTisrepresentableifthereisalistofingredientsasabove,withonlythekernelsκtallowedtodependonµ

(T)T1T2

orK,suchthatµ=κ#(µL⊗µ⊗⊗µ⊗⊗···).LLIfanexchangeabilitycontext(T,Γ)issuchthatallexchangeablelawsonKTarerepre-sentableforanycompactmetricKthenweshallsaythat(T,Γ)alwaysadmitsrepresen-tation.

Wemuststressthatourchosendefinitionofrepresentabilityisnotcompletelycanon-ical:althoughweareguidedbytheclassicalrepresentationtheoremsforhypergraph-exchangeablelawsandtheirrelatives,theseleadingexamplesaresufficientlycloselyre-latedonetoanotherthatitisnotquiteclearwhichfeaturesoftheirrepresentationtheoremsweshouldtrytokeep,andwhichtodiscard,whenabstractingtoamoregeneraldefinition.Thechoicewehavemadeseemstobesimpleandnatural,andalsotoreflectmanyoftheusestowhichtheserepresentationtheoremsareput(see[17]),butcertainlyithasalsobeenselectedpartlybecauseitworksforwhatfollows.Analternativeformulationoftherepresentationtheoremforexchangeablearrayscanbegiveninsteadinterms,forexample,ofsequencesofauxiliarycompactmetricspacesZ0,Z1,Z2,...andindexsetsT1,T2,...withΓ-actionsα1,α2,...fromwhichallexchangeablelawsarethenobtainedaspushfor-T1

wardsofprobabilitymeasuresontheproductspaceZ0×Z1×···thatareinvariantundertheassociatedoverallcoordinate-permutingactionofΓandhavetheadditionalpropertythatthecoordinatesinZi+1areconditionallyindependentgiventhecoordinatesinev-eryZjforj≤i.Therepresentationtheoremforexchangeablearraysistreatedintheseterms,forexample,in[6],wherethischoiceisdictatedbytheusetowhichthattheoremisthenputinSection3of[7];however,theformalismofrepresentabilityextractedthiswayseemsmuchlessamenabletoourneeds,aswellasfurtherfromtheclassicaldescriptionsofAldousandKallenberg,andsowehavesettledfortheaboveinstead.

InourpresenttermsthemainRepresentationTheoremofAldous,HooverandKallenberg󰀁S󰀂

forhypergraph-exchangeablelawswithT:=kandΓ:=Sym0(S)withitscanonicalactionmaybewrittenasfollows.

Theorem2.3(RepresentationTheoremforhypergraph-exchangeablelaws).Ahypergraph-5

󰀁󰀂

exchangeablelawµisrepresentableusingthedataTi:=Sfori≤kandTk+1=

󰀁t󰀂󰀁iS󰀂

Tk+2=...=triv.,thedependencymapsφi:t→ifort∈kandi≤kandφi≡∅ifi≥k+1,andsomedeterministicmapsκtthatdependontheparticularchoiceofµ.Althoughwehaveallowedarbitraryprobabilitykernelsκtinourpresentformalism,intheaboveconcreterepresentationtheorem(anditsrelativesinsuchworksas[2,15])theyarealldeterministicmaps.However,asimpletransferargumentshowsthatthisdifferenceispurelycosmetic.

Lemma2.4.A(T,Γ)-exchangeablelawisrepresentableifandonlyifitisrepresentableusingdeterministicmapsκt:[0,1]×[0,1]φ1(t)×[0,1]φ2(t)×···→K.

ProofClearlyrepresentabilityusingdeterministicmapsamountstoaspecialcaseofrepresentability,soweneedonlyprovethatanyrepresentablelawisrepresentableusingdeterministicmaps.However,ifwehavealistofingredientsthatrepresentsµwithkernelsκt,thenbythestandardTransferTheorem(Theorem6.10inKallenberg[16])wemayfinddeterministicmaps

󰀁󰀂

θt:[0,1]×[0,1]×[0,1]φ1(t)×[0,1]φ2(t)×···→K

κt(x0,x1,...,·)=µL

󰀌

󰀎

y∈[0,1]:θt(y,x0,x1,...)∈·.

suchthat

Now,asisstandard,theLebesguespaces([0,1],µL)and([0,1]×[0,1],µL⊗µL)areisomorphic,sayviatheBorelmapξ:[0,1]→[0,1]2,andsonowdefining

κ˜t(x0,x1,...):=θt(ξ(x0),x1,...)

wecancheckatoncefromtheaboverelationsthatthesedeterministicmapsalsorepresent

theoriginallawµ.

3Bauersimplicesfromexchangeability

WewillnowprovethatifΓisamenableandtheexchangeabilitycontext(T,Γ)alwaysadmitsrepresentationthenitssimplicesPrΓKTofexchangeablelawsmustbeBauerforanyK.WewillalsogiveadirectdeductionofthisBauerpropertyintherepresentativeexampleofhypergraphexchangeabilitywithoutusingrepresentability,bothforcomplete-nessandbecauseitseemsinterestingtocomparethisdirectproofwithargumentstoprovethePoulsenpropertyinthecaseofcube-exchangeabilityinthenextsection.

6

3.1TheBauerpropertyfromrepresentability

Lemma3.1.IfΓisamenable,andifan(T,Γ)-exchangeableprobabilitymeasureµ∈PrΓKTisrepresentableatall,thenitisergodicifandonlyifitisrepresentablebykernelsκtnotdependingonthefirstcoordinate.

T1⊗T2⊗···

ProofFirstsupposethatµisergodic,andwriteitasκ#µ∗⊗forsomesuitableL

φ1(t)

familyκ.Nowdefinethefamilyκuofkernelsκu×[0,1]φ2(t)×···󰀃Kt:[0,1]×[0,1]byκut(x0,x1,...):=κt(u,x1,...)(thismakessenseandisunambiguousuptoequalityforalmosteveryu);clearlynoneofthesedependsonthefirstcoordinatein[0,1]×[0,1]φ1(t)×

(T)T1⊗T2⊗···

···,andalsoeach(κu)#µ∗⊗isanotherΓ-invariantprobabilityonKTsuchthatL

(T)

µ=

󰀆

10

T1⊗T2⊗···

(κu)#µ∗⊗du.L

(T)

(T)

T1⊗T2⊗···

Bytheergodicityofµthisdecompositionmustbetrivial,andso(κu)#µ∗⊗=µLforalmost-everyu;hencealmostanyofthekernelfamiliesκuwillsuffice.

Nowsuppose,ontheotherhand,thateachκtdoesnotdependonthefirstcoordinatein[0,1]×[0,1]T1×···,andthatA,B⊆KTaretwoBorelfinite-dimensionalcylindersets,saydeterminedbythefinitesetsofcoordinatesI,Jrespectively.ThenbyourassumptionthatallorbitsofΓonTandonTiareinfiniteandthatΓisamenable,itfollowsthatforsomedensity-1subsetofF⊂Γwehaveφi(g(I))∩φi(J)=∅forallg∈F.However,thisimpliesthatκtandκshavenoargumentsincommonfort∈g(I)ands∈J,andsothesetsτg(A)andBmustbeindependentunderµ.Infactthisprovesnotonlyergodicity,butevenweakmixing,andwearedone.

Proposition3.2(RepresentabilityimpliesBauer).IfΓisamenableandtheexchangeabil-itycontext(T,Γ)alwaysadmitsrepresentationthenPrΓKTisaBauersimplexforanycompactmetricK.

ProofWeknowthatPrΓKTisacompactconvexsetandthatitsextremepointsarepreciselythosemembersthatcanberepresentedbysomecollectionofkernelsκtnotdependingonthefirstcoordinatein[0,1]×[0,1]φ1(t)×···;thusweneedonlyshowthatif

(T)T1⊗T2⊗···

µn=(κn)#µ∗⊗areavaguelyconvergentsequenceofsuchmeasuresthentheirL

limitµadmitsasimilarrepresentation.

T1⊗T2⊗···

However,foreachtthekernelκtdefinesajoiningoftheprobabilitymeasuresµ∗⊗L

and(πt)#µnontheproductspace[0,1]×[0,1]φ1(t)×···×Kunderwhichtheveryfirstcoordinateisindependentfromalltheothers(becauseκtdoesnotdependonthis

7

coordinate),andso,passingtoasubsequenceifnecessary,wemayassumethatthesejoiningsalsoconvergetosomefixedprobabilitymeasureλ∞,tonthisproductspace.Itisclearthatthisnewmeasurewillstillhaveprojectiononto[0,1]×[0,1]φ1(t)×···equaltoT1⊗T2⊗···µ∗⊗andwillstillenjoytheindependenceofthefirstcoordinatefromeverythingL

else,andsoifwenowdisintegratetheseλ∞,toverthatfirstprojectionwerecoverkernelsκ∞,tthatalsodonotdependontheveryfirstcoordinateandrepresentµ,asrequired.RemarkIdonotknowwhethertheassumptionofamenabilitycouldberemovedfromtheprecedingarguments.⊳

3.2TheBauerpropertyintheparticularcontextofhypergraphex-changeability

Beforemovingon,letusincludeasecondproofthattheclassicalhypergraph-exchangeabilitycontexthastheBauerpropertythatusesonlyaveryelementarypropertyenjoyedbythatcontext,ratherthantherepresentationtheorem.Thissubsectionisnotessentialtothemainthreadofthisnote,butisincludedmainlytoadvertisethequestionofwhethertheargumentthatitcontainscanbegeneralizedfurther.

Definition3.3(Distantmultipletransitivity).Weshallwritethatanexchangeabilitycon-text(T,Γ)isdistantlymultiplytransitive(DMT)ifforanyfiniteI,J⊂TthereissomesubsetE⊆Γofdensity1andsuchthatforanyγ1,γ2∈Ethereissomeξ∈Γwithξ↾I=idIandξ◦γ1↾J=γ2↾J.

ItisimmediatetocheckthatthehypergraphexchangeabilitycontextisDMT,andsothefollowingresultappliestothatcontextinparticular.

Proposition3.4(DMTimpliesBauer).IfΓisamenableand(T,Γ)isDMTthenithastheBauerproperty.

ProofWefollowcloselytheanalogousargumentofGlasnerandWeissin[9].SupposethatΓisamenable,that(T,Γ)isDMT,thatµ∈PrΓKTcanbevaguelyapproximatedbyergodicmeasures,andthatA∈ΣKTisinvariantwitha:=µ(A)∈[0,1].Foranyε>0thereareafinitesetJ⊂T󰀋andacontinuousfunctionf:KJ→[0,1]suchthat󰀜1A−f◦πJ󰀜L1(µ)<ε,andhenceKTf◦πJdµ≈εa.FromtheinvarianceofAitfollowsthatweactuallyhave󰀜1A−f◦πJ◦τγ󰀜L1(µ)<εforanyγ∈Γ.

Now,since(T,Γ)isDMTandJisfinite,thereissomeE⊆Γwithasymptoticdensity1suchthatforanyγ1,γ2∈Ethereissomeξ∈Γsuchthatξ↾J=idJ,andsof◦πJ◦τξ=

8

f◦πJ,whereasξ◦γ1↾J=γ2↾Jandsof◦πJ◦τγ1◦τξ=f◦πJ◦τγ2.Letusnowfixsomerepresentativememberγ0∈E.

Next,sincef◦πJand(f◦πJ)·(f◦πJ◦τγ0)arecontinuous,byassumptionwecanalwaysfindsomeergodicµ′∈PrΓKTwith

󰀆󰀆

f◦πJdµ′≈εf◦πJdµ

KT

KT

and

󰀆

KT

(f◦πJ)·(f◦πJ◦τγ0)dµ′≈ε

󰀆

KT

(f◦πJ)·(f◦πJ◦τγ0)dµ.

Letting(In)n≥1beaFølnersequenceinΓ,itfollowsfromtheergodicityofµ′that1

|IN|γ∈I

󰀃󰀆

N

KT

(f◦πJ)·(f◦πJ◦τγ)dµ′≈ε

≈ε

󰀆

󰀆

KT

(f◦πJ)·(f◦πJ◦τγ0)dµ′

󰀆

1A·1Adµ=µA=a.

KT

(f◦πJ)·(f◦πJ◦τγ0)dµ≈2ε

KT

Combiningtheseapproximationsshowsthata≈6εa2foranyε>0,andsoinfactwe

musthavea∈{0,1},andµmustitselfbeergodic.

4ThePoulsenpropertyforcube-exchangeablemeasures

Wewillnowshowthat,quiteunlikethecasesstudiedintheprevioustwosections,if(T,Γ)isthecube-exchangeabilitycontext(andKisnontrivial)thenPrΓKTisactuallythePoulsensimplex.ThisargumentisalsocloselymotivatedbythatofGlasnerandWeissin[9],wheretheyshowthatinthecaseoftheexchangeabilitycontext(Γ,RΓ)comprisingagroupΓanditsright-regularrepresentationonitself,thesimplexPrΓ{0,1}ΓofinvariantprobabilitymeasuresiseitherBauerorPoulsenpreciselyaccordingasΓhas

9

orfailsKazhdan’sproperty(T).Noconditionlikeproperty(T)willenterouranalysis—indeed,thegroupsofimmediateinteresttousarealllocallyfinite,hencetriviallyamenable—butwewillfollowcloselythebasicstepsoftheirconstruction.

Thereareessentiallytwoofthesesteps.WefirstshowthatincaseK={0,1}theparticu-δofanon-ergodicmemberofPrΓ{0,1}Tisvaguelyapproximablebylarexample1

21

membersthatarenotonlyergodic,butactuallyweaklymixing;andthenweusethisfactthroughtheconstructionofacertainjoiningtoshowthatquitegenerallywheneverµ1andµ2inPrΓKTareapproximablebyergodicmeasures,soistheiraverage1µ.We22

needtoensureweakmixinginthefirststepbecauseweshallneedtoensuretheergodicityofacertainproductinthesecond,butthismakeslittledifferencetotheotherdetailsoftheproofs.ItiseasytoseethatthisthenimpliesthePoulsenproperty.

N⊕N1

Lemma4.1.Let(T,Γ)=(F⊕2,IsomF2).ThenthemeasureisvaguelyapproximablebyweaklymixingmembersofPrΓ{0,1}T.

Γ

δ∈Pr{0,1}T12

ProofWeneedtoshowthatforanyε>0andN≥1thereissomestronglymixing

measureµ∈PrΓ{0,1}Tsuchthatboth

µ{ω∈{0,1}T:ω↾FN=0}≥2

1

2

−ε.

Therearemanypossiblewaystoconstructsuchaµ;thefollowingseemstobeoneofthe

simplest.Wespecifyµasthelawofthememberof{0,1}Toutputbythefollowingrandomprocedure.Foranyp∈[0,1]letνpbetheproductmeasureonFN=1}=p2withνp{z:zi󰀉

⊕N

foreveryi∈N;andforanyz=(zi)i∈N∈FNdefine󰀚x,z󰀛:=i∈Nxizi2andx∈F2

mod2(thissumbeingactuallyalwaysfinite).Nowletµbethelawofthecharacteristic

N

functionoftherandomsubset{x∈F⊕:󰀚x,z󰀛+η=0mod2}wherez∼νpforsome2

verysmallp>0andη∈F2ischosenindependentlyanduniformlyatrandom.

ItisclearthatthisµisΓ-invariantandstronglymixingprovidedp=0,butifpisverysmallthenforourchosenNwehaveνp{z:z1=z2=...=zN=0}≥1−ε,andconditionedontheevent{z:z1=z2=...=zN=0}wemusthavealso

󰀅1ifη=0(occurswithprob.1

=1{x∈FN

2:󰀏x,z󰀐+η=0mod2}),2whichprovesthedesiredvagueapproximationto

10

1

δ.21

N⊕N

Theorem4.2.Thecube-exchangeabilitycontext(T,Γ)=(F⊕2,IsomF2)hasthePoulsenproperty.

ProofLetKbeanycompactmetricspacecontainingatleasttwopoints.AsarguedbyGlasnerandWeissin[9],itsufficestoprovethatforanytwoergodicµ1,µ2∈PrΓKT,theiraverage1µcanbeapproximatedbyergodicmembersofPrΓKT;forthenit22

followsbyrepeatedapproximationthattheergodicprobabilitymeasuresmustbedenseintheirownconvexhull,butthisisthewholeofPrΓKT.

Thus,itisenoughtoshowthatforanyε>0andfinitelistofcontinuousfunctionsf1,f2,...,fm:KT→[0,1]thereissomeergodicµ∈PrΓKTsuchthat

󰀆󰀆

1

fidµ2∀i≤m.fidµ≈2ε

2TTKKMoreover,bytheStone-WeierstrassTheoremwemayassumeeachfidependsonlyon

coordinatesinsomefixedfinitesubsetJ⊂T,andsomayfactorizeandrewriteitasfi◦πJ.

First,letuschooseµ0∈PrΓ{0,1}Tweaklymixingandsatisfyingµ0(A)≈ε1

T

δ(A)forallA⊆{0,1}dependingonlyoncoordinatesinJ;thisispossibleby12

Lemma4.1.Nowconsideranyergodiccube-exchangeablejoiningλofthetwomea-suresµ1andµ2ontheproductspace(K2)T(suchcanbeobtained,forexample,bytakinganyergodiccomponentofthesimpleproductµ1⊗µ2),andnowfromthisconstructtheproductµ0⊗λ,amemberofPrΓ({0,1}×K2)T.Sinceµ0isweaklymixing,thisproductisstillergodic.

WenowcompletetheproofbyspecifyingaΓ-equivariantmapψ:({0,1}×K2)T→KTwhoselawasaKT-valuedrandomvariableunderµ0⊗λwillbetheergodicapproxi-matingmeasurethatweseek:givenapoint(η,ω(1),ω(2))∈({0,1}×K2)T,wedefine

(1)(2)

ψ(η,ω(1),ω(2))ttobeωtifηt=0,andωtifηt=1.Letusalsowriteψ(1)andψ(2)fortheusualprojectionmaps({0,1}×K2)T→KTontothefirstandsecondcopiesofKTrespectively.

Itisclearthatthisψisequivariant,andthatitslawψ#(µ0⊗λ)must,likeµ0⊗λ,be

11

ergodic.Finally,

󰀆󰀆

fi◦πJdψ#(µ0⊗λ)=fi◦πJ◦ψd(µ0⊗λ)T2TK({0,1}×K)󰀆󰀆=fi◦πJ◦ψd(µ0⊗λ)+fi◦πJ◦ψd(µ0⊗λ)

{η↾J=0}{η↾J=1}󰀆+fi◦πJ◦ψd(µ0⊗λ)

∁∁{η↾J=0}∩{η↾J=1}

󰀆󰀆

≈εµ0{η↾J=0}·fi◦πJ◦ψ(1)dλ+µ0{η↾J=1}·fi◦πJ◦ψ(2)dλ

(K2)T(K2)T

󰀆

1

fi◦πJdµ2,≈ε

2KTwherewehavededucedfromtheknownqualityofourapproximationµ0≈

µ0{η↾J=0},µ0{η↾J=1}≈ε

1

1

δ21

that

•Firstselectg0∈Uuniformlyatrandom;

◦

•Nowselect󰀉gi∈Uforeachi∈Nindependentlyatrandomwithlawν,andlet

N◦

gv:=g0+i∈Nvigiforallv=(vi)i∈N∈F⊕2.

TheSym0(N)-symmetry(‘hypergraph-exchangeability’)ofthislawµismanifest;inordertoguaranteefullcube-exchangeabilityitturnsouttobenecessaryandsufficientthatνsatisfythesymmetryconditionthatthetwomaps(g0,g1)→(g0,g0+g1)and(g0,g1)→(g0+g1,g0)havethesamelawundertheproductmeasureµU⊗ν0.

NoticethatwehavealreadymetoneoftheseAbeliangroupexamplesintheformofthemeasureµconstructedfromνpduringtheproofofLemma4.1.

Cube-exchangeablesystemsofthisform(or,moregenerally,factorsofsuchsystems)aresurelyratherspecial,buttheyfitintoaconsiderablymoregeneralframework,andthismayaffordsomegreaterpurchaseoverthegeneralcase.Letusapproachthisgeneralizationfromaratherdifferentdirection.

SinceUisanAbeliangroupwemaydescribeageneralpointofUF2usingaM¨obius

N⊕N

inversionformula:forany(gv)v∈F⊕N∈UF2thereareunique(uα)α∈(N)∈U(<∞)such

2<∞

that󰀃󰀃󰀈󰀄󰀊

N

viuα∀v∈F⊕gv=uα=2,i∈αα⊆v−1{1}α∈(∞)anditisroutinetocheckthattheresultingbijectionΦ:U

omorphism,andthatitiscovariantforthecoordinate-permutingactionsofSym0(N)onthedomainandonthetarget.Itfollowsthatanyhypergraph-exchangeableµ∈PrSym0(N)UT

N

ispushedforwardbyΦtoahypergraph-exchangeablemeasureΦ#µonU(<∞),andindeedthatthisgivesanaffinehomeomorphismbetweenthesimplicesofhypergraph-exchangeablemeasures.However,thestrongerassumptionthatµbecube-exchangeableisthencon-vertedunderΦintoaratherlargersetofadditionalsymmetriesforΦ#µ,andthesearenotobviouslyeasiertodescribeexplicitlythantheoriginalcube-exchangeablestructureofµ.Indeed,ifµ∈PrΓKTforanarbitrarycompactmetricspaceKandtheone-dimensionalmarginals(πv)#µ∈PrK(whichmustallagree)areatomless,thenwecansimplychooseanynon-discretecompactAbeliangroupUandafunction(K,(π0)#µ)→(U,µU)thatdefinesameasure-algebra-isomorphismandobservethatapplyingthisfunctionpointwise

⊕N⊕N

givesanisomorphismfromΓ󰀆KF2toΓ󰀆UF2,andsowithoutanyadditionalas-sumptionstheaboveexamplesofcube-exchangeablelawsonAbeliangroupslosenogen-eralityatall.However,wemightaskwhetherwecanfindaroutetoamoreinterestingrep-resentationtheoremthroughacannychoiceoftheisomorphism(K,(π0)#µ)→(U,µU),

13

NF⊕2

N

(<→U∞)isactuallyahome-⊕N

forwhichtheadditionalconstraintsonthejointlawof(uα)α∈(N)canthenbedescribed

<∞

explicitly.Alittlemoregenerally,canwesomeUandsomecube-exchangeablemeasure

⊕N

θonUF2ofanespeciallysimpleformsuchthatµisacoordinatewisefactorofθ,say

⊕N

µ=(fF2)#θforsomeBorelf:U→K.Forexample,canwechooseaθunderwhichthesummandsintheM¨obiusinversionformulacorrespondingtosetsofdifferentsizesareindependent?

Wewillnotoffersomuchhere,butmerelynotethatmorecanbesaidincertainsimplecases.Forexample,ifuα=0a.s.whenever|α|≥2,thentheabovelawsµmustbemeasuresofthekinddescribedinAldous’example,asmaybecheckedbyhandfromtherank-2caseofthehypergraph-exchangeabilityrepresentationtheoremappliedtoΦ#µ.Moregenerally,wecanfocusattentiononthesub-simplicesofcube-exchangeablelawsthatareconcentratedoncertainΓ-invariantclosedsubsetsofKT.Foreachr≥1letΩr

⊕N

bethesubsetofthoseg∈UF2withthepropertythat‘allr-facessumtozero’:

󰀃

N

g∈Ωr⇔gv=0foreachr-faceF⊆F⊕2.

v∈F

ThissuggestionismadebyAldousin[4](example16.20),wherehealsopointsoutthat

somesuchrestrictedmeasuresalreadydefeatanyoverly-simpleapproachtoarepresenta-tiontheoremforcube-exchangeabilityusinggrouprandomwalks.

ItiseasytocheckthatconcentrationonΩ2isequivalenttotheabovementionedconditionthatuα=0a.s.whenever|α|≥2.ItturnsoutthatinthespecialcaseU=F2thepoints

⊕N

ofΩrhaveaparticularlysimpleexplicitdescription:inthiscase,identifyingUF2asthe

N

spaceoffunctionsF⊕→F2,anexplicitcalculationoftheM¨obiusinversiongivesat2

N

oncethatafunctiong:F⊕→F2liesinΩrifandonlyifitisapolynomialofdegree2

atmostr.(NotethatforageneralfieldKitisfairlystraightforwardtoprovethatthosefunctionsf:Kd→Kthathavezerosumacrossanyaffinecopyofther-dimensionaldiscretecubeinKdmustbeapolynomialofdegreeatmostr,foranyunderlyingfieldK.However,underthepresentweakerassumptionofzero-sumsacrossonlyisometriccopiesofther-cubeinFd2,anditisnothardtofindexamplesshowingthattheimplicationofdegree-rpolynomialityfollowsonlyoverthesmallestfieldF2.)

5.2Thegeometryofsubsimplicesandrelationstopropertytesting

¯’-Theorem4.2hasconsequencesfortherelationsbetweenthevaguetopologyandthe‘d(orjoining)topology(consideredbyAldousinthecaseofhypergraphexchangeability

14

¯-metricρonexchangeablein[3]andSection15of[4]).Thislatterisdefinedbythed

probabilitymeasures,givenby

ρ(µ,ν):=

λ∈J(µ,ν)

inf

λ{(ω,η)∈KT×KT:ωv=ηv}

forany(arbitrary)choiceofreferenceindexv∈T,whereJ(µ,ν)denotesthecollectionofalljoiningsofµandν:Γ-invariantprobabilitymeasuresonKT×KThavingfirstmarginalµandsecondmarginalν.Ifρ(µ,ν)issmallweshallwriteinformallythatµandνhaveanear-diagonaljoining.

Thejoiningtopologyisclearlyatleastasstrongasthevaguetopology,andingeneralitisstrictlystronger(see[3],forexample).However,givenaΓ-invariantclosedsubsetΩ⊆KT,wecanconsiderthesubsimplexPrΓΩ⊆PrΓKTofexchangeablemeasuresconcentratedonΓ,andaskwhetherthetwodifferentneighbourhoodbasesofthissubsim-plexdefinedbythesetwotopologiesmightcoincide.Thisquestionismotivatedbythecaseofhypergraph-exchangeability,forwhichitcanbeprovedthatthesebasesdoalwayscoincide;thisfollows,inparticular,fromtherathermorepreciseresultsforsuchclosedsubsetscontainedin[7].However,bymakingreferencetothePoulsenproperty,wecanseethatthisisnotalwaysthecaseforcube-exchangeability.

Proposition5.1.Ifanexchangeabilitycontext(T,Γ)hasthePoulsenpropertyandthesetwoneighbourhoodbasesaroundPrΓΩareequivalentthenPrΓΩmustalsobethePoulsensimplex.

ProofIngeneral,ifµ1isergodicandisclosetoµ2inthevaguetopology,itneednotfollowthatµ1isclosetoanyoftheergodiccomponentsofµ2inthevaguetopology.However,ifinfactµ1isjoining-closetoµ2thenitdoesfollowsthatitisjoining-closetomanyoftheergodiccomponentsofµ2,byconsideringtheergodicdecompositionofthejoiningitself.

Letthesituationbeasdescribed,andsupposethatµ∈PrΓΩ;wemustshowthatµisvaguelyapproximablebyextremepointsofPrΓΩ.SincePrΓΩisjustthesubsetofthosemembersofPrΓKTthatareconcentratedonΩ,itsextremepointsarestilljustitsergodicmembers.

BythePoulsenpropertyofPrΓKT,weknowµcanbevaguelyapproximatedbyergodicmeasuresinthislargersimplex.Ontheotherhand,bytheassumedequivalenceofthetwoneighbourhoodbases,itfollowsthatprovidedtheseapproximatingmeasuresarecloseenoughtothesubsimplexPrΓΩforthevaguetopology,theyactuallyhavenear-diagonaljoiningswithmembersofthissmallersimplexPrΓΩ.

However,ifµ1∈PrΓKTisergodicandλ∈PrΓ(KT×KT)isanear-diagonaljoiningofµ1tosomememberofPrΓΩ,thenthecomponentsoftheergodicdecompositionofλmust

15

(almostsurely)bejoiningsofµ1toergodicmeasuresthatarestillmembersofPrΓΩ,andinorderthatλbenear-diagonaltheseergodiccomponentsofλmustalsobenear-diagonalwithhighprobability.Itfollowsthatµ1mustactuallybejoining-close,andhencevaguelyclose,tosomeergodicmembersofPrΓΩ;andsinceµ1wasitselfvaguelyclosetoµ,wededucethatµmustbevaguelyapproximablebyextremepointsofPrΓΩ,asrequired.Wesuspectthattheaboveimplicationcannotbereversed(inthattherearealsoΩforwhichtheneighbourhoodbasesdonotcoincide,butforwhichPrΓΩisPoulsenanyway).Corollary5.2.ThesubsetΩ2⊆issuchthatthejoiningneighbourhoodbasisofthesimplexPrΓΩ2isstrictlystrongerthanthevagueneighbourhoodbasis.

ProofBythepreviousproposition,itsufficestoarguethatPrΓΩ2isnotPoulsen;how-ever,asdiscussedintheprevioussubsection,themembersofPrΓΩ2arepreciselyAldous’randomwalkexamplesinthecaseU=F2,anditisnoweasytocheckfromthisthatthesimplexinquestionhassetofextremepointspreciselythemeasuresµconstructedfromνpfordifferentp>0fromtheproofofLemma4.1,togetherwithδ0andδ1,andthatthissetofextremepointshasonlytheoneadditionalnon-ergodicclusterpoint1δ21(indeed,thatlemmaitselfguaranteesthatthismustbeclusterpoint;itistheargumentofTheorem4.2thatthennecessarilytakesusoutsidePrΓΩ2,andsodoesnotapplytothissub-simplex).Thus,PrΓΩ2cannotbePoulsen.

Inthesettingofhypergraphexchangeability,itturnsoutthatthereisacloserelation-shipbetweenpropertiesofthesub-simplexPrTΩandoftheconditionsonapointofKTneededtoguaranteemembershipofΩ.Inaddition,itturnsoutthatthislattermembershipconditioncanbeidentifiedsimplywithsomehereditarypropertyofK-colouringsoffinitehypergraphs(precisely,sothatapointofKTliesinΩifandonlyifwhenregardedasaK-colouredhypergraphallofitsfiniteinducedcolouredsub-hypergraphshavethathereditaryproperty).Fromthisvantagepoint,asuitableanalysisofthissimplexcanbeconvertedintoaproofthatallsuchpropertiesare‘efficientlytestable’(followingessentiallyatrans-lationofolder,purelycombinatorialargumentstothateffect;see,inparticular,AlonandShapira[5]andR¨odlandSchacht[18]).Weshallnotenterintothesenotionsfurtherhere,butreferthereadertothecompleteaccountin[7].

Itseemsclearthatasimilarnotionofefficienttestabilitycanbeformulatedinthesettingofdiscretecubesandtheirisometries:ingeneral,wewouldwritethatapropertyPofallsubsetsoffacesofthefinitediscretecubesFN2istestableifforanyε>0therearesomeN(ε)≥J(ε)≥1andδ(ε)>0suchthat,ifN≥N(ε)andE⊆FN2,andifweknowthataJ(ε)-faceFofFN2chosenuniformlyatrandomhasprobabilityatleast1−δ(ε)of

′′N

havingF∩E∈P,thenthereissomeE′⊆FN2havingE∈Pand|E∆E|<ε2.AlthoughwearenotawareofarigorousrelationshipbetweenthequestionofProposi-16

N

F⊕2F2

tion5.1andtestability,byanalogywiththeresultsof[7]wesuspectfromthatPropositionthatthepropertyΩ2isnottestable;andinfactadirectre-writeoftheparticularinfinitaryproofswehavegiveninfinitarytermsinahigh-dimensionalcubeFN2showsthatthisisso;weomitthedetails.

5.3Affinetransformationsoftheinfinite-dimensionaldiscretecube

Wehavealreadydiscussedcube-exchangeabilityasastrengtheningoftheconditionofhypergraph-exchangeabilitytreatedbyclassicalexchangeabilitytheory.However,itmay

N

beworthrecallingthatanevenstrongerexchangeabilitycontextonT=F⊕hasalso2

appearedimplicitlyinanumberofrecentworks,withΓthegroupofallaffinetransforma-tionsofT.

Inparticular,thissettingcloselyrelatestoseveralquestionsofcurrentinterestinarithmeticcombinatoricsconcerningthecountingofaffinecopiesofvariouspatterns(suchasfinite-dimensionalcubes)insubsetsofFN2forlargeN.Thesequestionsoftencorrespondnat-⊕N

N

urallytodescriptionsofprobabilitymeasureson{0,1}F2thatareAffF⊕2-invariantviaasuitablecorrespondenceprinciple,analogoustothewell-knownFurstenbergcorrespon-denceprinciplerelatingsubsetsofZtomeasure-preservingZ-actions(see,forexample,Furstenberg’sbook[8]).Closely-relatedtothislineofresearchistheinvestigationofthe‘Gowers-inverseconjecture’ofGreenandTaointhecaseofthevectorspacesFN2,whicharephrasedintermsofcorrelationsofindividualC-valuedfunctionsonFN2withfunc-tionsofcertainspecialforms.However,thisconjecturehasrecentlybeenshowntofailingeneralinthissettinginthepaper[10]ofGreenandTao,andsosomemorecomplicatedkindsofingredientseemtoberequiredforsuchastructuretheorem.

Inourmoreinfinitaryset-up,wesuspectthatinthepresenceofthisratherstrongersym-metryamuchmoredetailedanalysisofthestructureoftheexchangeablemeasuresispos-sible,andthatsuchananalysiswillprobablyrelyonmoreergodic-theoretictools(suchasthosedevelopedfortheprooforconvergenceandexpressionofthelimitofnonconven-tionalergodicaveragesinthecaseofZ-systems;see,inparticular,theworksofHost&Kra[14]andZiegler[?]);however,wehavenotinvestigatedthispossibilityfurther.WealsodirectthereadertoSubsection4.7of[6]foraveryinformaldiscussionofthedifferentapproachestotheextractionofstructuralinformationforinvariantmeasuresinthestudyofexchangeability,ontheonehand,andergodictheoryontheother.

17

5.4ThePoulsenpropertyforotherexchangeabilitycontexts

WesuspectthattheconclusionofTheorem4.2holdsmuchmoregenerally:thatforanamenablegroupΓitisonlyinthepresenceofsomeveryspecialexchangeabilitycontext(suchasthosethatareDMT)thatthePoulsenpropertyfails.

Isitpossibletoformulateamoregeneralconditionunderwhichanexchangeabilitycon-texthasthePoulsenpropertythatwillsubsumeTheorem4.2?Ontheotherhand,istheresomeconditionrelatedtothatofbeingDMTthatisactuallyequivalenttotheBauerprop-erty(possiblyonlyforamenableΓ)?CanthesimplexPrΓKTeverbeneitherBauernorPoulsen?

5.5Cube-exchangeabilityforfiner-grainedcubes

Wesuspectthattheresultsofthispaperextendtotheanalogousdefinitionofexchange-abilityonthefiner-grainedcubes(Z/mZ)⊕Nform>2(indeed,thesituationthereissurelyevenmorewild,ifanything),butitisnotclearwhethertheseexhibitanyadditionalnewphenomena.

References

[1]D.J.Aldous.Representationsforpartiallyexchangeablearraysofrandomvariables.

J.MultivariateAnal.,11(4):581–598,1981.[2]D.J.Aldous.Onexchangeabilityandconditionalindependence.InExchangeability

inprobabilityandstatistics(Rome,1981),pages165–170.North-Holland,Amster-dam,1982.¯-topologies.InExchangeabilityinprob-[3]D.J.Aldous.Partialexchangeabilityandd

abilityandstatistics(Rome,1981),pages23–38.North-Holland,Amsterdam,1982.´[4]D.J.Aldous.Exchangeabilityandrelatedtopics.InEcoled’´et´edeprobabilit´es

deSaint-Flour,XIII—1983,volume1117ofLectureNotesinMath.,pages1–198.Springer,Berlin,1985.[5]N.AlonandA.Shapira.ACharacterizationofthe(natural)GraphProperties

TestablewithOne-SidedError.preprint,availableonlineat

http://www.math.tau.ac.il/˜nogaa/PDFS/heredit2.pdf.

18

[6]T.Austin.Onexchangeablerandomvariablesandthestatisticsoflargegraphsand

hypergraphs.ProbabilitySurveys,(5):80–145,2008.[7]T.AustinandT.Tao.Onthetestabilityandrepairofhereditaryhypergraphproper-ties.preprint,availableonlineatarXiv.org:0801.2179,2008.[8]H.Furstenberg.ErgodicbehaviourofdiagonalmeasuresandatheoremofSzemer´edi

onarithmeticprogressions.J.d’AnalyseMath.,31:204–256,1977.[9]E.GlasnerandB.Weiss.Kazhdan’spropertyTandthegeometryofthecollection

ofinvariantmeasures.GeometricandFunctionalAnalysis,7:917–935,1997.[10]B.J.GreenandT.Tao.Thedistributionsofpolynomialsoverfinitefields,withappli-cationstothegowersnorms.preprint,availableonlineatarXiv.org:0711.3191,2007.[11]E.HewittandL.J.Savage.SymmetricmeasuresonCartesianproducts.Trans.Amer.

Math.Soc.,80:470–501,1955.[12]D.N.Hoover.Relationsonprobabilityspacesandarraysofrandomvariables.1979.[13]D.N.Hoover.Row-columnsexchangeabilityandageneralizedmodelforexchange-ability.InExchangeabilityinprobabilityandstatistics(Rome,1981),pages281–291,Amsterdam,1982.North-Holland.[14]B.HostandB.Kra.Nonconventionalergodicaveragesandnilmanifolds.Ann.Math.,

161(1):397–488,2005.[15]O.Kallenberg.Symmetriesonrandomarraysandset-indexedprocesses.J.Theoret.

Probab.,5(4):727–765,1992.[16]O.Kallenberg.Foundationsofmodernprobability.ProbabilityanditsApplications

(NewYork).Springer-Verlag,NewYork,secondedition,2002.[17]O.Kallenberg.Probabilisticsymmetriesandinvarianceprinciples.Probabilityand

itsApplications(NewYork).Springer,NewYork,2005.[18]V.R¨odlandM.Schacht.Generalizationsoftheremovallemma.preprint,available

onlineat

http://www.informatik.hu-berlin.de/

˜schacht/pub/preprints/gen_removal.pdf.

19

DEPARTMENTOFMATHEMATICS

UNIVERSITYOFCALIFORNIAATLOSANGELESLOSANGELES,CA90095-1555,USA

Email:timaustin@math.ucla.edu

Web:http://www.math.ucla.edu/˜timaustin

20