The ordering principle in a fragment of approximate counting

The O de ing P inciple in a F agmen o App oxima e Coun ing Albe A se ias∗Neil Thapen† Oc obe 28, 2013 Abs ac The o de ing p inciple s a es ha e e y ini e linea o de has a leas elemen . We show ha , in he ela i ized se ing, he su jec i e weak pigeonhole p inciple o polynomial ime unc ions does no p o e a He b andized e sion o he o de ing p inciple o e T1 2. This answe s an open ques ion aised in [Buss, Ko lodziejczyk and Thapen, 2012] and comple es hei p og am o compa e he s eng h o Jeˇ ´abek’s bounded a i hme ic heo y o app oxima e coun ing wi h weakened e sions o i . 1 In oduc ion We show ha , in he ela i ized se ing, he su jec i e weak pigeonhole p inciple o polynomial ime unc ions does no p o e he He b andized o de ing p inciple o e T1 2. This answe s an open ques ion om [2]. In he es o his sec ion we will gi e a b ie in oduc ion o his p oblem. We will assume a basic knowledge o he language and heo ies o bounded a i hme ic; s anda d e e ences a e [1] and [10]. The He b andized o de ing p inciple HOP is a o mula in he ocabula y α= (≺, h), whe e ≺is a bina y ela ion symbol and his a una y unc ion symbol. I asse s ha i ≺is a s ic linea o de ing o an in e al [n] := ∗Depa amen de Llengua ges i Sis emes In o m`a ics. Uni e si a Poli `ecnica de Ca alunya, Ba celona, Spain ([email p o ec ed]). Resea ch pa ially suppo ed by TIN2010-20967-C04-05 (TASSAT). †Ins i u e o Ma hema ics. Academy o Sciences o he Czech Republic, P ague, Czech Republic ([email p o ec ed]). Resea ch pa ially suppo ed by g an IAA100190902 o GA AV ˇ CR, and by Cen e o Excellence CE-ITI unde g an P202/12/G061 o GA ˇ CR and RVO: 67985840. 1 {0, . . . , n −1}and hmaps [n] in o [n], hen he e is some x∈[n] such ha h(x) is no he immedia e p edecesso o x. In o he wo ds, ei he he e exis s a wi ness ha ≺is no a s ic linea o de ing o [n], o he e exis s x∈[n] such ha h(x)6≺ x, o he e exis x, y ∈[n] such ha h(x)≺y≺x. The p inciple is exp essed by a Σb 1(α) o mula ∃z <n3(θ(z, n)) whe e zcodes a possible wi ness ( he bigges o which would be a iple wi nessing ha ≺ is no ansi i e) and θis a quan i ie - ee PV(α) o mula. We no e ha he na u al He b andiza ion o he o de ing p inciple would no con ain he las condi ion, abou hgi ing he immedia e p edecesso . As in [2], including his condi ion is con enien and also makes he p inciple weake , and hence makes ou unp o abili y esul s onge . Simila p inciples o HOP (wi hou his condi ion) ha e appea ed as he gene alized i e a ion p inciple in [4] and as He b andized minimiza ion in [5]. To de ine he su jec i e weak pigeonhole p inciple sWPHP, we i s in- oduce some no a ion: o a unc ion (¯z, x) o se e al a gumen s, we will some imes ea some o he a gumen s as pa ame e s and w i e hem as subsc ip s, w i ing, o example, ¯z(x) o conside ed as a amily o one- a gumen unc ions pa ame ized by ¯z. Gi en a unc ion symbol , he o mula sPHPa b( ) exp esses ha , i b > a, hen is no a su jec ion om [a] on o [b]. We ake he p inciple sWPHP(PV(α)) o be he o mula ∀a∀esPHPa a2(ge) whe e g(e, x) is a “uni e sal” polynomial ime unc ion (wi h o acle α) which we can hink o as, o example, e alua ing he Boolean ci cui eon inpu x (whe e eis allowed “o acle ga es” o compu ing que ies o α). The p inciple exp esses ha no PV(α) unc ion wi h pa ame e s is a su jec ion om [a] on o [a2], o any a > 1. I is a long-s anding open p oblem o sepa a e Buss’ hie a chy Ti 2o bounded a i hme ic heo ies by sen ences o ixed complexi y. This is un- known e en o he ela i ized hie a chy Ti 2(α) (al hough he e is such a sepa a ion known o he hie a chy Ti 1(α), which has polynomial a he han quasipolynomial g ow h a e [6]). Techniques exis o sepa a e PV(α) om T1 2(α), and T1 2(α) om T2 2(α), by ∀Σb 1(α) sen ences [4]. Bu hese do no seem o be use ul in he case o T2 2(α) and T3 2(α). The ecen pape [2] ies o app oach his p oblem om a di e en di- ec ion by conside ing, a he han T2 2, Jeˇ ´abek’s heo y T1 2+sWPHP(PV2) o app oxima e coun ing [9]. He e PV2s ands o a se o e ms naming all FPNP unc ions. This heo y is called APC2in [2], and si s a a simila le el 2 in he hie a chy o T2 2. The au ho s do no show any sepa a ion o APC2 om any hing highe , bu do gi e ∀Σb 1(α) sepa a ions o ce ain sub heo ies o APC2(α) om T2 2(α) and APC2(α) i sel . In pa icula , hey obse e ha HOP is p o able in bo h APC2(α) and T2 2(α) and show, among o he hings, ha PV(α) + sWPHP(PV2(α)) 6` HOP.1 Ou esul is ha T1 2(α) + sWPHP(PV(α)) 6` HOP. This esol es an open ques ion in [2] and shows ha weakening APC2(α), ei he by educing he amoun o induc ion om Σb 1(α) o Σb 0(α) ( ha is, om T1 2(α) o PV(α), see [7]), o by educing he unc ions o which sWPHP holds om PV2(α) o PV(α), gi es a s ic ly weake heo y. In Sec ion 2 below we gi e he high-le el p oo o ou esul , and in Sec ions 3 and 4 we p o e some necessa y echnical lemmas. The mos impo an o hese is Lemma 3, which shows how decision ees compu ing unc ions in PV(α) a e simpli ied unde a ce ain andom es ic ion. In Sec ion 5 we discuss a p oposi ional e sion o ou esul . We a e g a e ul o Em´ıl Jeˇ ´abek and Leszek Ko lodziejczyk o help ul commen s on ea lie e sions o his wo k. 2 Main heo em We begin wi h some s anda d manipula ions. Lemma 1. Suppose φ(n)is a Σb 1(α) o mula and T1 2(α) + sWPHP(PV(α)) ` ∀n(φ(n)). Then he e is a e m = (n)and a unc ion symbol ∈PV(α)such ha T1 2(α)` ∀n( > 2∧ ∀ < 2∃u< ( n(u) = ∨φ(n))). 1The e is a echnical issue he e conce ning ou de ini ion o sWPHP. The e a e h ee e sions conside ed in he pape [2]: ha he e is no su jec ion om [a] on o [a(1+1/|a|)]; om [a] on o [2a]; o om [a] on o [a2]. The no a ion sWPHP is used o mally in [2] only o he i s (and s onges ) e sion, while we, o he sake o simplici y, use i o mean he hi d (and weakes ). Fo ou esul , as in mos cases, his makes no di e ence, because he h ee e sions a e equi alen o e S1 2(α) o PV(α) unc ions. Howe e in he esul om [2] e e ed o he e i does ma e which e sion is used, because o PV2(α) unc ions hey a e unlikely o be equi alen o e PV(α) (see [8]). P ecisely, he esul is o [a] on o [2a], and hence also o [a] on o [a2]. I is no known o [a] on o [a(1 +1/|a|)]. 3 P oo . This is p o ed by s anda d icks abou ampli ying ailu es o he weak pigeonhole p inciple (see o example [13]). In de ail, we a e gi en a PV(α) unc ion symbol g(e, x) such ha T1 2(α) + ∀a∀esPHPa a2(ge)` ∀n(φ(n)). By Pa ikh’s heo em, he e is a e m p=p(n) such ha T1 2(α)` ∀n∃a<p∃e<p ¬sPHPa a2(ge)∨φ(n). We may assume wi hou loss o gene ali y ha T1 2(α) p o es p > 1. By Co olla y 2.2 o [13] he e is a PV(α) unc ion symbol G(e, a, b, x) such ha , in any model o S1 2(α) (and in pa icula any model o T1 2(α)), i geis a su jec ion om aon o a2 hen Ge,a,b is a su jec ion om aon o b. Le (n, u) be he unc ion : (n, (e, a, x)) 7→ G(e, a, p6, x) whe e in e p e s i s second a gumen uas a iple (e, a, x) o numbe s, each in [p]. Then whene e he e exis eand ain [p] such ha geis a su jec ion om aon o a2, we also ha e ha nis a su jec ion om [p3] on o [p6]. The lemma ollows by pu ing =p3. Theo em 1. T1 2(α) + sWPHP(PV(α)) 6` HOP. P oo . We assume he opposi e o each a con adic ion. By Lemma 1 we ha e a e m = (n) and unc ion symbol ∈PV(α) such ha T1 2(α)` ∀n( > 2∧ ∀ < 2∃u< ∃z <n3( n(u) = ∨θ(z, n))) (1) whe e wand θ(z, n) a e he bounding e m and he quan i ie - ee PV(α)- o mula, espec i ely, om he Σb 1(α)- o mula exp essing HOP. By [3], his is wi nessed by a PLS p oblem2, as ollows. The p oblem is gi en by a e m s=s( , n), a cos unc ion Cand a neighbo hood unc ion Non [s], whe e Cand N ake nand as pa ame e s, un in ime polynomial in |n|, and ha e o acle access o ≺and h. A solu ion o he p oblem is a numbe x∈[s] such ha C(N(x)) ≥C(x). The e is a polynomial ime educ ion unc ion g(which does no access he o acles) such ha o all 2Ou e sion o he PLS wi nessing heo em is sligh ly di e en om he one ha appea s in [3]. Howe e hei PLS p oblem (FL, cL, NL) is easily educible o ou s, by pu ing C(x) = cL(x) and N(x) = NL(x) o x∈FL, and pu ing C(x) = q+ 1 and N(x) = 0 o x /∈FL, whe e qis an uppe bound on he cos in hei ins ance. 4 choices o o acles ≺and h, o all nand and all x∈[s], i xis a solu ion o he p oblem hen g(x) is a wi ness hu, zi o he exis en ial quan i ie s on he igh -hand side o (1). Be o e we con inue we need some de ini ions. Le n,pand qbe posi i e in ege s such ha qdi ides pand p/q < n −p. Le m=p/q. A andom es ic ion ρwi h hese pa ame e s is a pa i ion o [n] in o linea ly o de ed se s chosen andomly as ollows: 1. choose a andom se B0⊆[n] o ca dinali y n−p, 2. andomly pa i ion [n] B0in o blocks B1, . . . , Bqo ca dinali y m, 3. choose a andom linea o de ing ≺io each Bi o i∈ {0, . . . , q}. The condi ions on n,pand qimply ha m<n−p. Consequen ly we will call B0 he big block and he o he blocks small blocks. Fo e e y x∈ [n], we w i e Bx o he unique block ha con ains x. Le R(n, p, q) be he se o all es ic ions ρwi h pa ame e s n,pand qas abo e. I ρ= (B0, . . . , Bq,≺0,...,≺q) is a es ic ion in R(n, p, q) wi h blocks B0, . . . , Bq and linea o de ings ≺0,...,≺q, we say ha a o al linea o de ing ≺o [n] is compa ible wi h ρi i sa is ies h ee condi ions: 1. ≺ex ends ≺i o e e y i∈ {0,...q}, 2. Biis ≺-con ex3 o e e y i∈ {0, . . . , q}, and 3. x≺y o e e y x∈[n] B0and e e y y∈B0. No ice ha he e a e always exac ly q! o al linea o de ings compa ible wi h ρ, co esponding o he q! possible ways o a anging he small blocks B1, . . . , Bqbelow he big block B0. We con inue wi h he p oo . Le n0be a la ge in ege , and le n≥n0 be an exac eigh h powe , so ha p:= n1/2and q:= n1/8a e bo h in ege s. No e ha m:= p/q =n3/8is also an in ege . Gi en a o al linea o de ing ≺ o [n] le h≺be he p edecesso unc ion a ising om ≺, excep ha h(z) = z o he ≺-minimum elemen z∈[n], and also h(z) = z o e e y z6∈ [n]. We will call o acles (≺, h≺) o his o m s anda d. We say ha such an o acle is compa ible wi h a es ic ion ρi ≺is compa ible wi h ρ. Lemma 2. The e is a es ic ion ρ∈ R(n, p, q)wi h n,pand qas speci ied, and a numbe ∈[ 2], such ha o e e y u∈[ ]we ha e n(u)6= unde e e y s anda d o acle (≺, h≺)compa ible wi h ρ. 3I (S, <) is a linea ly o de ed se , we say ha a subse C⊆Sis <-con ex i whene e xand ybelong o Cand zin Sis such ha x < z and z < y, hen also zbelongs o C. 5 The p oo o his lemma akes up Sec ions 3 and 4 o his pape . We show now how we use i o ob ain a con adic ion. Le ρand be gi en by he lemma. Le |n|kbe a bound on he numbe o o acle que ies and eplies ha can occu in a compu a ion o he cos o neighbou hood unc ions Co N. Fo la ge enough n, we may assume ha 3|n|k+ 3 < q. Le Abe he se o pa ially-de ined o acles α= (≺, h) a ising in he ollowing way. Choose `≤ |n|ko he small blocks o ρ and a ange hem in any o de as Bi1, . . . , Bi`. Le he domain o ≺be he union o all hese blocks oge he wi h B0, and le ≺be a o al linea o de ing o his domain, wi h he o de ing inside each block gi en by ρand he o de ing be ween blocks gi en by Bi1≺ · · · ≺ Bi`≺B0. Le hbe de ined e e ywhe e on his domain excep o i s ≺-minimum elemen , as he p edecesso unc ion a ising om ≺. Le Mbe he se o pai s (x, α) o x∈[s] and α∈A o which he cos Cα(x) o xunde αis de ined. We claim ha Mis non-emp y, and ha o any (x, α)∈M, he e is (y, β)∈Msuch ha Cβ(y)< Cα(x). Toge he hese imply a con adic ion, since cos s mus be posi i e. To see ha Mis non-emp y, we simula e a compu a ion o C(0), con- s uc ing a pa ial o acle αas we go. A he beginning o he simula ion, we se α o be he o de ing ≺gi en by ρon B0and unde ined elsewhe e, wi h he co esponding p edecesso unc ion hde ined on B0wi hou i s ≺-minimum elemen . Each ime a que y is made abou any elemen zcu - en ly ou side he domain o ≺, we add he block Bzcon aining z o he bo om o ou o de ing ≺and ex end happ op ia ely, in pa icula se ing h(w) o be w0, whe e wis he minimum elemen o ou cu en o de ing and w0is he maximum elemen o he new block. I h(z) is que ied whe e zis cu en ly he ≺-minimum elemen , we ake any unused block and simila ly add i o he bo om o he o de ing. We add a mos |n|k< q blocks o e he cou se o he simula ion, so ne e un ou o unused blocks o add in his second case. Gi en (x, α) in M, o ind a sui able (y, β) in Mwe simula e a compu a- ion o N(x), sa e his alue as y, and hen simula e a compu a ion o C(y), all using a pa ial o acle γwhich we cons uc as we go. A he beginning we se γ o be α. We ex end γas needed du ing he simula ion, as in he p e ious pa ag aph. As 3|n|k< q, we ne e un ou o unused blocks. To cons uc β, i s emo e om γe e y block ha does no appea in o acle que ies o eplies in he compu a ion o Cγ(y). Then adjus h o skip o e any holes, so ha o each block Bexcep o he bo om-mos , h(w) = w0 whe e wis he minimum elemen o Band w0is he maximum elemen o he block below B. This canno change he compu a ion o C(y), since i 6 h(w) had been que ied in ha compu a ion hen he eply would ha e come om he block B0immedia ely below Bin γ, and hence we would no ha e emo ed B0. Since he compu a ion o Cγ(y) makes a mos |n|kque ies, he esul ing βbelongs o A. I emains o show ha Cβ(y)< Cα(x). I is enough o show Cγ(y)< Cγ(x). Suppose no . Then unde any s anda d o acle γ0which ex ends γ and is compa ible wi h ρwe ha e Cγ0(Nγ0(x)) ≥Cγ0(x), implying ha xis a solu ion o ou PLS p oblem in γ0and hus, by he p ope ies o ρ, ha g(x) is a pai hu, ziwhe e zis a wi ness o HOP. Conside ed as such a wi ness, zmen ions a mos h ee elemen s o [n]. We cons uc a pa icula such γ0 om γby i s adding o he bo om o ou o de ing he blocks con aining hose o he h ee elemen s which a e no ye in he domain o γ, and hen all he emaining blocks in any o de . No e ha , as 3|n|k+ 3 < q, we added a leas one block below he h ee elemen s men ioned in z. Finally we le h(x) = x o he minimal elemen xo he o al o de ing we ha e cons uc ed and o e e y x6∈ [n]. Thus γ0is a s anda d o acle, compa ible wi h ρ, in which zdoes no wi ness HOP because h(w) is he immedia e p edecesso o w o each elemen o [n] men ioned in z. This comple es he p oo . 3 F ames and ame decision ees The compu a ion o an o acle Tu ing machine can be modeled by a decision ee, in which each in e nal node is labeled wi h an o acle que y and has child en co esponding o he possible eplies, and each lea is labeled wi h an ou pu alue. In his sec ion we de ine a pa icula kind o ee compu ing he unc ion n(u) om Lemma 2 unde s anda d o acles. In Sec ion 4 we will show ha , o a andom es ic ion ρ, he expec ed numbe o pa hs h ough he ee consis en wi h ρ, and hence he expec ed numbe o ou pu alues o n(u) ha can occu o e all s anda d o acles consis en wi h ρ, is small (in ac i is less han 2, i nis la ge enough). Lemma 2 will ollow easily. The p oo o his bound is complica ed by he ac ha in ou andom e- s ic ions o acle eplies a e no independen o each o he , which will equi e us o wo k wi h condi ional p obabili ies. To conside , b ie ly, a simple ex- ample, suppose ha ou machine only que ied a una y o acle o a subse Ao [n]. Fix a small p obabili y pand le σbe he usual andom es ic- ion which independen ly se s each bi o A o 0 o 1, each wi h p obabili y (1 −p)/2, o lea es i unse wi h p obabili y p. Le Tbe a ee model- ing compu a ions o he machine, whe e we may assume ha no bi o A 7 is que ied mo e han once along any pa h. Le be any node in T. The expec ed numbe o eplies consis en wi h σ o he que y x∈A? labeling is hen 2p+(1−p) = 1+p. I is s aigh o wa d o show (as in he i s pa o he p oo o Lemma 3 below) ha he expec ed numbe o pa hs h ough Tconsis en wi h σis hus a mos (1 + p)d, whe e dis he heigh o T. Re u ning o ou p oo , le n, nand be as in he p oo o Theo em 1. We may assume wi hou loss o gene ali y, by adding dummy o acle que ies as necessa y, ha he machine compu ing n(u) on a s anda d o acle wo ks in he ollowing way. I main ains a se S⊆[n] o poin s and some o al o de ing ≺o S. Fu he mo e o some pai s x, y ∈Si knows ha h(x) = y. I can ask wo kinds o o acle que y. The i s is an o de ing que y, o x∈[n] S. This in ol es w i ing x? on he o acle ape, and ge ing as a eply he posi ion o xin he o acle’s o de ing ≺wi h espec o all elemen s o S. Assuming ha ≺is a linea o de ing, he e a e a mos |S|+1 possible eplies. The second is a p edecesso que y, o x∈Swhe e h(x) is no known. This in ol es w i ing h(x)? on he o acle ape, and ge ing as a eply some y∈[n]. The e a e a mos npossible eplies. Finally he compu a ion ou pu s some ∈[ 2]. In he es o his sec ion we gi e a o mal de ini ion o ames and ame decision ees, which we will use o model compu a ions o n(u) on s anda d o acles. A ame consis s o : 1. a se S⊆[n], 2. a linea o de ing ≺o S, 3. a pa i ion C0, . . . , C −1o Sin o ≺-con ex se s. Each Ciis called an h-chain. I Cis an h-chain, we w i e min(C) and max(C) o i s minimum and maximum elemen s in he linea o de ing ≺, espec- i ely. We always assume ha he pa i ion o Sin o h-chains C0, . . . , C −1 is gi en in he o de induced by ≺on hei leas elemen s, which by ≺- con exi y means ha min(Ci−1)max(Ci−1)≺min(Ci)max(Ci) o e e y i∈ {1, . . . , −1}. Fo e e y xin S, we w i e Cx o he unique h-chain ha con ains x. The unique ame wi h emp y Sis called he emp y ame. A o al linea o de ing ≺0o [n] is compa ible wi h Si ≺0ex ends ≺, and e e y h-chain in S emains ≺0-con ex. A ame decision ee (FDT) is a ee whose nodes a e labeled by ames sa is ying ce ain condi ions, which we desc ibe below. Each lea node is 8 assigned an ou pu , which is an elemen o [ 2]. Each non-lea node labeled by a ame (S, ≺, C0, . . . , C −1) is assigned one o wo ypes o que ies: an o de ing que y x? o some xin [n] S, o a p edecesso que y h(x)? o some xin Swi h x= min(Cx). A node labeled by an o de ing que y has +1 child en, one o each iin {0, . . . , }. The child co esponding o i∈ {0, . . . , }is an FDT whose oo is labeled by a ame de i ed om he ame o i s pa en by ex ending S o S∪{x}, ex ending he linea o de ing ≺ o y≺x o e e y y∈C0∪. . .∪Ci−1 and x≺y o e e y y∈Ci∪ · · · ∪ C −1, and wi h he ollowing pa i ion o S∪ {x}in o h-chains: C0, . . . , Ci−1,{x}, Ci, . . . , C −1. Fo a node labeled by a p edecesso que y, he e a e wo cases. The i s case occu s i Cx=C0, ep esen ing he si ua ion in which xis he smalles elemen o S. In his case he ee has one child o each possible eply z in [n] S, and one ex a child, ep esen ing he possibili y ha h(x) = x. The child co esponding o z∈[n] Sis an FDT whose oo is labeled by he ame ha has Sex ended o S∪{z}, he linea o de ing ≺ex ended o z≺y o e e y yin S, and he ollowing pa i ion o S∪ {z}in o h-chains: {z} ∪ C0, C1, . . . , C −1. The child co esponding o he eply h(x) = xis an FDT whose oo is labeled by he same ame as i s pa en . The second case occu s i Cx=Ci o some i > 0, ep esen ing he si ua ion in which he e a e al eady elemen s o Ssmalle han x. In his case he ee has one child o each zin [n] Sand one child o z= max(Ci−1). The child co esponding o z∈[n] Sis an FDT whose oo is labeled by he ame ha has Sex ended o S∪{z}, he linea o de ing ≺ex ended o y≺z o e e y y∈C0∪ · · · ∪ Ci−1and z≺y o e e y y∈Ci∪ · · · ∪ C −1, and he ollowing pa i ion o S∪ {z}in o h-chains: C0, . . . , Ci−1,{z} ∪ Ci, Ci+1, . . . , C −1. The child co esponding o z= max(Ci−1) is an FDT whose oo is labeled by he ame ha has he same se S, he same linea o de ing ≺, and he ollowing pa i ion o Sin o h-chains: C0, . . . , Ci−2, Ci−1∪Ci, Ci+1, . . . , C −1. I π= (S, ≺, C0, . . . , C −1) is a ame and ρ= (B0, . . . , Bq,≺0,...,≺q) is a es ic ion om R(n, p, q), we say ha ρand πa e compa ible, deno ed 9 [12] M. Lau ia, Sho Res*(polylog) Re u a ions i and only i Na ow Res Re u a ions. Manusc ip , a ailable a a Xi :1310.5714, 2011. [13] N. Thapen, A model- heo e ic cha ac e iza ion o he weak pigeonhole p inciple. Annals o Pu e and Applied Logic, 118:175-195, 2002. 16