text: D D (S) diﬀers from (T), or g∗(S) diﬀers from g∗(T), or both of them occur. Therefore, it is necessary to D D consider two kinds of diﬀerences: the diﬀerence between the input-space distributions (S) and (T) and the diﬀerence between the labeling functions g∗(S) and g∗(T). Next, we will show that the integral probability metric DF(S, T ) can be bounded by using two separate quantities that can measure the D D diﬀerence between (S) and (T) and the diﬀerence between g∗(S) and g∗(T), respectively. D D As shown in (13), the quantity disc ( (S), (T)) actually measures the diﬀerence between the input- D D (cid:96) space distributions (S) and (T). Moreover, we introduce another quantity to measure the diﬀerence between the labeling functions g∗(S)(cid:12)(cid:12) and g(cid:0)∗(T): (cid:1) G (cid:0) (cid:1)(cid:12)(cid:12) Deﬁnition 3.2 Given a loss funct(cid:12)ion (cid:96) and a function class , we deﬁne (cid:12) − Q(GT)(g∗(S), g∗(T)) := sup E(T)(cid:96) g (x(T)), g∗(T)(x(T)) E(T)(cid:96) g (x(T)), g∗(S)(x(T)) . (16) ∈G 1 1 g1 G F Note that if both of the loss function (cid:96) and the function class are non-trivial (or is non-trivial), the quantity Q(GT)(g∗(S), g∗(T)) is a (semi)metric between the labeling functions g∗(S) and g∗(T). In fact, it is not hard to verify that Q(GT)(g∗(S), g∗(T)) satisﬁes the triangle inequality and is equal to zero if g∗(S) and g∗(T) match. (cid:12) (cid:12) (cid:12) (cid:0) (cid:1) (cid:0) (cid:1)(cid:12) By combining (10), (13) and (16(cid:12)), we have (cid:12) disc (D(S), D(T)) = sup(cid:12)(cid:12) E(S(cid:0))(cid:96) g (x(S)), g (x(S))(cid:1) − E(T)(cid:96)(cid:0) g (x(T)), g (x(T)) (cid:1)(cid:12)(cid:12) (cid:96) ∈(cid:12)G 1 2 1 2 (cid:12) g1,g2 ≥ sup (cid:12)(cid:12)E(S)(cid:96)(cid:0)g (x(S)), g∗(S)(x(S))(cid:1) − E(T)(cid:96)(cid:0)g (x(T)), g∗(S)(x(T))(cid:1) ∈G (cid:12) 1 1 g1 = sup E(S(cid:0))(cid:96) g (x(S)), g∗(S)(x(S(cid:1))) − E(T(cid:0))(cid:96) g (x(T)), g∗(T)(x(T(cid:1))(cid:12)(cid:12)) ∈G 1 1 (cid:12) g1 (cid:12) (cid:12) (cid:12) (cid:0) −(cid:1) (cid:0) (cid:1)(cid:12) + E((cid:12)T)(cid:96) g (x(T)), g∗(T)(x(T)) E(T)(cid:96) g (x(T)), g∗(S)(x(T)) (cid:12) 1 1 ≥ sup E((cid:12)(cid:12)S)(cid:96) g (cid:0)(x(S)), g∗(S)(x(S)) −(cid:1)E(T)(cid:96) g (cid:0)(x(T)), g∗(T)(x(T)) (cid:1)(cid:12)(cid:12) ∈G (cid:12) 1 1 (cid:12) g1 − − sup E(T)(cid:96) g (x(T)), g∗(T)(x(T)) E(T)(cid:96) g (x(T)), g∗(S)(x(T)) ∈G 1 1 g1 − =DF(S, T ) Q(GT)(g∗(S), g∗(T)), and thus ≤ D D DF(S, T ) disc ( (S), (T)) + Q(GT)(g∗(S), g∗(T)), (17) (cid:96) which implies that the integral probability metric DF(S, T ) can be bounded by the summation of the D D discrepancy distance disc ( (S), (T)) and the quantity Q(GT)(g∗(S), g∗(T)), which measure the diﬀerence (cid:96) D D between the input-space distributions (S) and (T) and the diﬀerence between the labeling functions g∗(S) and g∗(T), respectively. Compared with (11) and (15), the integral probability metric DF(S, T ) provides a new mechanism to capture the diﬀerence between two domains, where the diﬀerence between labeling functions g∗(S) and g∗(T) is measured by a (semi)metric Q(GT)(g∗(S), g∗(T)). Remark 3.1 As shown in (10) and (13), the integral probability metric DF(S, T ) takes the supremum G D D G of g over , and the discrepancy distance disc ( (S), (T)) takes the supremum of g and g over (cid:96) 1 2 8

text: D

text: D

text: (S)

text: diﬀers

text: from

text: (T),

text: or

text: g∗(S)

text: diﬀers

text: from

text: g∗(T),

text: or

text: both

text: of

text: them

text: occur.

text: Therefore,

text: it

text: is

text: necessary

text: to

text: D

text: D

text: consider

text: two

text: kinds

text: of

text: diﬀerences:

text: the

text: diﬀerence

text: between

text: the

text: input-space

text: distributions

text: (S)

text: and

text: (T)

text: and

text: the

text: diﬀerence

text: between

text: the

text: labeling

text: functions

text: g∗(S)

text: and

text: g∗(T).

text: Next,

text: we

text: will

text: show

text: that

text: the

text: integral

text: probability

text: metric

text: DF(S,

text: T

text: can

text: be

text: bounded

text: by

text: using

text: two

text: separate

text: quantities

text: that

text: can

text: measure

text: the

text: D

text: D

text: diﬀerence

text: between

text: (S)

text: and

text: (T)

text: and

text: the

text: diﬀerence

text: between

text: g∗(S)

text: and

text: g∗(T),

text: respectively.

text: D

text: D

text: As

text: shown

text: in

text: the

text: quantity

text: disc

text: (S),

text: (T))

text: actually

text: measures

text: the

text: diﬀerence

text: between

text: the

text: input-

text: D

text: D

text: space

text: distributions

text: (S)

text: and

text: (T).

text: Moreover,

text: we

text: introduce

text: another

text: quantity

text: to

text: measure

text: the

text: diﬀerence

text: between

text: the

text: labeling

text: functions

text: and

text: G

text: Deﬁnition

text: Given

text: a

text: loss

text: and

text: a

text: function

text: class

text: we

text: deﬁne

text: Q(GT)(g∗(S),

text: g∗(T))

text: sup

text: g

text: (x(T)),

text: g∗(T)(x(T))

text: g

text: (x(T)),

text: g∗(S)(x(T))

text: ∈G

text: G

text: F

text: Note

text: that

text: if

text: both

text: of

text: the

text: loss

text: function

text: and

text: the

text: function

text: class

text: are

text: non-trivial

text: (or

text: is

text: non-trivial),

text: the

text: quantity

text: Q(GT)(g∗(S),

text: g∗(T))

text: is

text: a

text: (semi)metric

text: between

text: the

text: labeling

text: functions

text: g∗(S)

text: and

text: g∗(T).

text: In

text: fact,

text: it

text: is

text: not

text: hard

text: to

text: verify

text: that

text: Q(GT)(g∗(S),

text: g∗(T))

text: satisﬁes

text: the

text: triangle

text: inequality

text: and

text: is

text: equal

text: to

text: zero

text: if

text: g∗(S)

text: and

text: g∗(T)

text: match.

text: By

text: combining

text: and

text: we

text: have

text: disc

text: (D(S),

text: D(T))

text: g

text: (x(S)),

text: g

text: g

text: (x(T)),

text: g

text: (x(T))

text: sup

text: (x(S)),

text: (x(T)),

text: ∈G

text: sup

text: g

text: (x(S)),

text: g

text: (x(T)),

text: ∈G

text: g

text: (x(T)),

text: g∗(T)(x(T))

text: g

text: (x(T)),

text: g∗(S)(x(T))

text: sup

text: g

text: g∗(S)(x(S))

text: g

text: g∗(T)(x(T))

text: ∈G

text: sup

text: g

text: (x(T)),

text: g∗(T)(x(T))

text: g

text: (x(T)),

text: g∗(S)(x(T))

text: ∈G

text: =DF(S,

text: T

text: Q(GT)(g∗(S),

text: g∗(T)),

text: and

text: thus

text: D

text: D

text: DF(S,

text: T

text: disc

text: (S),

text: (T))

text: Q(GT)(g∗(S),

text: g∗(T)),

text: which

text: implies

text: that

text: the

text: integral

text: probability

text: metric

text: DF(S,

text: T

text: can

text: be

text: bounded

text: by

text: the

text: summation

text: of

text: the

text: D

text: D

text: discrepancy

text: distance

text: disc

text: (S),

text: (T))

text: and

text: the

text: quantity

text: Q(GT)(g∗(S),

text: g∗(T)),

text: which

text: measure

text: the

text: diﬀerence

text: D

text: D

text: between

text: the

text: input-space

text: distributions

text: (S)

text: and

text: (T)

text: and

text: the

text: diﬀerence

text: between

text: the

text: labeling

text: functions

text: g∗(S)

text: and

text: g∗(T),

text: respectively.

text: Compared

text: with

text: and

text: the

text: integral

text: probability

text: metric

text: DF(S,

text: T

text: provides

text: a

text: new

text: mechanism

text: to

text: capture

text: the

text: diﬀerence

text: between

text: two

text: domains,

text: where

text: the

text: diﬀerence

text: between

text: labeling

text: functions

text: g∗(S)

text: and

text: g∗(T)

text: is

text: measured

text: by

text: a

text: (semi)metric

text: Q(GT)(g∗(S),

text: g∗(T)).

text: Remark

text: As

text: shown

text: in

text: and

text: the

text: integral

text: probability

text: metric

text: DF(S,

text: T

text: takes

text: the

text: supremum

text: G

text: D

text: D

text: G

text: of

text: g

text: over

text: and

text: the

text: discrepancy

text: distance

text: disc

text: (S),

text: (T))

text: takes

text: the

text: supremum

text: of

text: g

text: and

text: g

text: over


text: 2 K. GRYGIEL, P. LESCANNE and occurrences of variables, which corresponds to the number of all vertices in the tree representing the given term. This size model, although natural from the combinatorial viewpoint, turned out to be diﬃcult to handle. The question that arises immediately concerns the number of λ-terms of a given size. This non-trivial task has been done by Bodini, Gardy, and Gittenberger in [1, 2] and Lescanne in [14]. The approach applied in the latter paper has been extended in [9] by the authors of the current paper to the model in which applications and abstractions are the only ones that contribute to the size of a λ-term. The same model has been studied in [4] by David et al., where several properties satisﬁed by random λ-terms are provided. When dealing with the two described models, it is not diﬃcult to deﬁne recur- rence relations for the number of λ-terms of a given size. However, by applying standard tools of the theory of generating functions one obtains generating func- tions that are expressed as inﬁnite sequences of radicals. Moreover, the radii of convergence are in both cases equal to zero, which makes the analysis of those functions very diﬃcult to cope with. In this paper, we study the binary encoding of lambda calculus introduced by John Tromp in [18]. This representation results in another size model. It comes from the binary lambda calculus he deﬁned in which he builds a minimal self inter- preter of lambda calculus1 as a basis of algorithmic complexity theory [15]. Set as a central question of theoretical computer science and mathematics, this approach is also more realistic for functional programming. Indeed for compiler builders it is counter-intuitive to assign the same size to all the variables, because in the trans- lation of a program written in Haskell, Ocaml or LISP variables are put in a stack. A variable deep in the stack is not as easily reachable as a variable shallow in the stack. Therefore the weight of the former should be larger than the weight of the latter. Hence it makes sense to associate a size with a variable proportional to its distance to its binder. In this model, recurrence relations for the number of terms of a given size are built using this speciﬁc notion of size. From that, we derive corresponding generating functions deﬁned as inﬁnitely nested radicals. However, this time the radius of convergence is positive and allows us for further analysis of the functions. We are able to compute the exact asymptotics for the number of all (not necessarily closed) terms and we also prove the approximate asymptotics for the number of closed ones. Moreover, we deﬁne an unranking function, i.e., a generator of terms from their indices from which we derive a uniform generator of λ-terms (general and typable). This allows us to provide outcomes of computer experiments in which we estimate the number of simply typable λ-terms of a given size. 2. Lambda calculus and its binary representation Lambda calculus is a model of computation that is equivalent to Turing machines or recursive functions, serving as a powerful tool in the development of the program- ming theory [16]. Furthermore, it constitutes the basis for functional programming languages and has many applications in automated theorem provers. Basic objects of the lambda calculus are λ-terms, which are regarded as denota- tion for functions or computer programs. Given a countable inﬁnite set of variables 1an alternative to universal Turing machine ##LTLine##

label: paragraph

text: K.

text: GRYGIEL,

text: P.

text: LESCANNE

text: and

text: occurrences

text: of

text: variables,

text: which

text: corresponds

text: to

text: the

text: number

text: of

text: all

text: vertices

text: in

text: the

text: tree

text: representing

text: the

text: given

text: term.

text: This

text: size

text: model,

text: although

text: natural

text: from

text: the

text: combinatorial

text: viewpoint,

text: turned

text: out

text: to

text: be

text: diﬃcult

text: to

text: handle.

text: The

text: question

text: that

text: arises

text: immediately

text: concerns

text: the

text: number

text: of

text: λ-terms

text: of

text: a

text: given

text: size.

text: This

text: non-trivial

text: task

text: has

text: been

text: done

text: by

text: Bodini,

text: Gardy,

text: and

text: Gittenberger

text: in

text: and

text: Lescanne

text: in

text: The

text: approach

text: applied

text: in

text: the

text: latter

text: paper

text: has

text: been

text: extended

text: in

text: by

text: the

text: authors

text: of

text: the

text: current

text: paper

text: to

text: the

text: model

text: in

text: which

text: applications

text: and

text: abstractions

text: are

text: the

text: only

text: ones

text: that

text: contribute

text: to

text: the

text: size

text: of

text: a

text: λ-term.

text: The

text: same

text: model

text: has

text: been

text: studied

text: in

text: by

text: David

text: et

text: al.,

text: where

text: several

text: properties

text: satisﬁed

text: by

text: random

text: λ-terms

text: are

text: provided.

text: When

text: dealing

text: with

text: the

text: two

text: described

text: models,

text: it

text: is

text: not

text: diﬃcult

text: to

text: deﬁne

text: recur-

text: rence

text: relations

text: for

text: the

text: number

text: of

text: λ-terms

text: of

text: a

text: given

text: size.

text: However,

text: by

text: applying

text: standard

text: tools

text: of

text: the

text: theory

text: of

text: generating

text: functions

text: one

text: obtains

text: generating

text: func-

text: tions

text: that

text: are

text: expressed

text: as

text: inﬁnite

text: sequences

text: of

text: radicals.

text: Moreover,

text: the

text: radii

text: of

text: convergence

text: are

text: in

text: both

text: cases

text: equal

text: to

text: zero,

text: which

text: makes

text: the

text: analysis

text: of

text: those

text: functions

text: very

text: diﬃcult

text: to

text: cope

text: with.

text: In

text: this

text: paper,

text: we

text: study

text: the

text: binary

text: encoding

text: of

text: lambda

text: calculus

text: introduced

text: by

text: John

text: Tromp

text: in

text: This

text: representation

text: results

text: in

text: another

text: size

text: model.

text: It

text: comes

text: from

text: the

text: binary

text: lambda

text: calculus

text: he

text: deﬁned

text: in

text: which

text: he

text: builds

text: a

text: minimal

text: self

text: inter-

text: preter

text: of

text: lambda

text: as

text: a

text: basis

text: of

text: algorithmic

text: complexity

text: theory

text: Set

text: as

text: a

text: central

text: question

text: of

text: theoretical

text: computer

text: science

text: and

text: mathematics,

text: this

text: approach

text: is

text: also

text: more

text: realistic

text: for

text: functional

text: programming.

text: Indeed

text: for

text: compiler

text: builders

text: it

text: is

text: counter-intuitive

text: to

text: assign

text: the

text: same

text: size

text: to

text: all

text: the

text: variables,

text: because

text: in

text: the

text: trans-

text: lation

text: of

text: a

text: program

text: written

text: in

text: Haskell,

text: Ocaml

text: or

text: LISP

text: variables

text: are

text: put

text: in

text: a

text: stack.

text: A

text: variable

text: deep

text: in

text: the

text: stack

text: is

text: not

text: as

text: easily

text: reachable

text: as

text: a

text: variable

text: shallow

text: in

text: the

text: stack.

text: Therefore

text: the

text: weight

text: of

text: the

text: former

text: should

text: be

text: larger

text: than

text: the

text: weight

text: of

text: the

text: latter.

text: Hence

text: it

text: makes

text: sense

text: to

text: associate

text: a

text: size

text: with

text: a

text: variable

text: proportional

text: to

text: its

text: distance

text: to

text: its

text: binder.

text: In

text: this

text: model,

text: recurrence

text: relations

text: for

text: the

text: number

text: of

text: terms

text: of

text: a

text: given

text: size

text: are

text: built

text: using

text: this

text: speciﬁc

text: notion

text: of

text: size.

text: From

text: that,

text: we

text: derive

text: corresponding

text: generating

text: functions

text: deﬁned

text: as

text: inﬁnitely

text: nested

text: radicals.

text: However,

text: this

text: time

text: the

text: radius

text: of

text: convergence

text: is

text: positive

text: and

text: allows

text: us

text: for

text: further

text: analysis

text: of

text: the

text: functions.

text: We

text: are

text: able

text: to

text: compute

text: the

text: exact

text: asymptotics

text: for

text: the

text: number

text: of

text: all

text: (not

text: necessarily

text: closed)

text: terms

text: and

text: we

text: also

text: prove

text: the

text: approximate

text: asymptotics

text: for

text: the

text: number

text: of

text: closed

text: ones.

text: Moreover,

text: we

text: deﬁne

text: an

text: unranking

text: function,

text: i.e.,

text: a

text: generator

text: of

text: terms

text: from

text: their

text: indices

text: from

text: which

text: we

text: derive

text: a

text: uniform

text: generator

text: of

text: λ-terms

text: (general

text: and

text: typable).

text: This

text: allows

text: us

text: to

text: provide

text: outcomes

text: of

text: computer

text: experiments

text: in

text: which

text: we

text: estimate

text: the

text: number

text: of

text: simply

text: typable

text: λ-terms

text: of

text: a

text: given

text: size.

text: Lambda

text: calculus

text: and

text: its

text: binary

text: representation

text: Lambda

text: calculus

text: is

text: a

text: model

text: of

text: computation

text: that

text: is

text: equivalent

text: to

text: Turing

text: machines

text: or

text: recursive

text: functions,

text: serving

text: as

text: a

text: powerful

text: tool

text: in

text: the

text: development

text: of

text: the

text: program-

text: ming

text: theory

text: Furthermore,

text: it

text: constitutes

text: the

text: basis

text: for

text: functional

text: programming

text: languages

text: and

text: has

text: many

text: applications

text: in

text: automated

text: theorem

text: provers.

text: Basic

text: objects

text: of

text: the

text: lambda

text: calculus

text: are

text: λ-terms,

text: which

text: are

text: regarded

text: as

text: denota-

text: tion

text: for

text: functions

text: or

text: computer

text: programs.

text: Given

text: a

text: countable

text: inﬁnite

text: set

text: of

text: variables

text: alternative

text: to

text: universal

text: Turing

text: machine

text: ##LTLine##


text: 12 K. GRYGIEL, P. LESCANNE n T0,n 0 0 1 0 n T∞,n 2 0 0 0 3 0 1 0 4 1 2 1 5 0 3 1 6 1 4 2 7 1 5 2 8 1 6 3 9 1 7 5 10 5 8 8 11 4 9 13 12 9 10 22 13 13 11 36 14 23 12 58 15 29 13 103 16 67 14 177 17 94 15 307 18 179 16 535 19 285 17 949 20 503 18 1645 21 795 19 2936 22 1503 20 5207 23 2469 21 9330 24 4457 22 16613 25 7624 23 29921 26 13475 24 53588 27 23027 25 96808 28 41437 26 174443 29 72165 27 316267 30 128905 28 572092 31 227510 29 1040596 32 405301 30 1888505 33 715078 31 3441755 34 1280127 32 6268500 35 2279393 33 11449522 36 4086591 34 20902152 37 7316698 35 38256759 38 13139958 36 70004696 39 23551957 37 128336318 40 42383667 38 235302612 41 76278547 39 432050796 42 137609116 40 793513690 43 248447221 41 1459062947 44 449201368 42 2683714350 45 812315229 46 1470997501 Figure 4. Number of typable terms left gives the number T of closed typable terms of size n and Figure 4 right gives 0,n the number T∞ of all typable terms of size n. ,n Thanks to the unranking function, we can build a uniform generator of λ-terms and, using this generator, we can build a uniform generator of simply typable λ- terms, which works by sieving the uniformly generated plain terms through a pro- gram that checks their typability (see for instance [9]). This way, it is possible to generate uniformly typable closed terms up to size 450 which is rather good since Tromp was able to build a self interpreter3 for the λ-calculus of size 210. 3Which is not typable by deﬁnition! ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: K.

text: GRYGIEL,

text: P.

text: LESCANNE

text: n

text: n

text: T∞,n

text: Figure

text: Number

text: of

text: typable

text: terms

text: left

text: gives

text: the

text: number

text: T

text: of

text: closed

text: typable

text: terms

text: of

text: size

text: n

text: and

text: Figure

text: right

text: gives

text: the

text: number

text: T∞

text: of

text: all

text: typable

text: terms

text: of

text: size

text: n.

text: ,n

text: Thanks

text: to

text: the

text: unranking

text: function,

text: we

text: can

text: build

text: a

text: uniform

text: generator

text: of

text: λ-terms

text: and,

text: using

text: this

text: generator,

text: we

text: can

text: build

text: a

text: uniform

text: generator

text: of

text: simply

text: typable

text: λ-

text: terms,

text: which

text: works

text: by

text: sieving

text: the

text: uniformly

text: generated

text: plain

text: terms

text: through

text: a

text: pro-

text: gram

text: that

text: checks

text: their

text: typability

text: (see

text: for

text: instance

text: This

text: way,

text: it

text: is

text: possible

text: to

text: generate

text: uniformly

text: typable

text: closed

text: terms

text: up

text: to

text: size

text: which

text: is

text: rather

text: good

text: since

text: Tromp

text: was

text: able

text: to

text: build

text: a

text: self

text: for

text: the

text: λ-calculus

text: of

text: size

text: is

text: not

text: typable

text: by

text: deﬁnition!

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: COUNTING BINARY LAMBDA TERMS 5 (cid:88) ∞ S (z) = S zn. m m,n n=0 Most of all, we are interested in the generating function for the number of closed terms, i.e., (cid:88) ∞ S (z) = S zn. 0 0,n n=0 Applying the recurrence on S , we get (cid:88) m,n ∞ S (z) = z2 (cid:88) S zn (cid:88) (cid:88) (cid:88) m m,n+2 n=0 ∞ ∞ ∞ ≥ n = z2 (cid:88)[m n + 1]zn + z2 Sm+1,n zn + z2 Sm,kSm,n−k zn n=0 n=0 n=0 k=0 − m 1 S S = z2 zk + z2 (z) + z2 (z)2 m+1 m k=0 − z2 (1 zm) S S = − + z2 (z) + z2 (z)2. 1 z m+1 m Solving the equation − S − S z2 (1 zm) S (3) z2 (z)2 (z) + − + z2 (z) = 0 m m 1 z m+1 gives us (cid:114) (cid:16) (cid:17) − − − S 1 1 4z4 1 −zm + (z) S 1 z m+1 (4) (z) = . m 2z2 S This means that the generating function (z) is expressed by means of inﬁn- m itely many nested radicals, a phenomenon which has already been encountered in previous research papers on enumeration of lambda terms, see e.g., [1]. However, in Tromp’s binary lambda calculus we are able to provide more results than in other representations of lambda terms. First of all, let us notice that the number of lambda terms of size n has to be less than 2n, the number of all binary sequences of size n. This means that in the considered model of lambda terms the radius of convergence of the generating function enumerating closed lambda terms is positive (even larger that 1/2), which is not the case in other models, where the radius of convergence is equal to zero. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: COUNTING

text: BINARY

text: LAMBDA

text: TERMS

label: equation

text: S

text: (z)

text: S

text: zn.

text: m

text: m,n

text: Most

text: of

text: all,

text: we

text: are

text: interested

text: in

text: the

text: generating

text: function

text: for

text: the

text: number

text: of

text: closed

text: terms,

text: i.e.,

text: S

text: (z)

text: S

text: zn.

text: Applying

text: the

text: recurrence

text: on

text: S

text: we

text: get

text: m,n

text: S

text: (z)

text: S

text: zn

text: m

text: n

text: n

text: zn

text: Sm,kSm,n−k

text: zn

text: m

text: S

text: S

text: zk

text: (z)

text: m

text: zm)

text: S

text: S

text: (z)

text: z

text: m

text: Solving

text: the

text: equation

text: S

text: S

text: zm)

text: S

text: (z)

text: (z)

text: m

text: m

text: z

text: gives

text: us

text: S

text: −zm

text: (z)

text: S

text: z

text: (z)

text: m

text: S

text: This

text: means

text: that

text: the

text: generating

text: function

text: (z)

text: is

text: expressed

text: by

text: means

text: of

text: inﬁn-

text: m

text: itely

text: many

text: nested

text: radicals,

text: a

text: phenomenon

text: which

text: has

text: already

text: been

text: encountered

text: in

text: previous

text: research

text: papers

text: on

text: enumeration

text: of

text: lambda

text: terms,

text: see

text: e.g.,

text: However,

text: in

text: Tromp’s

text: binary

text: lambda

text: calculus

text: we

text: are

text: able

text: to

text: provide

text: more

text: results

text: than

text: in

text: other

text: representations

text: of

text: lambda

text: terms.

text: First

text: of

text: all,

text: let

text: us

text: notice

text: that

text: the

text: number

text: of

text: lambda

text: terms

text: of

text: size

text: n

text: has

text: to

text: be

text: less

text: than

text: the

text: number

text: of

text: all

text: binary

text: sequences

text: of

text: size

text: n.

text: This

text: means

text: that

text: in

text: the

text: considered

text: model

text: of

text: lambda

text: terms

text: the

text: radius

text: of

text: convergence

text: of

text: the

text: generating

text: function

text: enumerating

text: closed

text: lambda

text: terms

text: is

text: positive

text: (even

text: larger

text: that

text: which

text: is

text: not

text: the

text: case

text: in

text: other

text: models,

text: where

text: the

text: radius

text: of

text: convergence

text: is

text: equal

text: to

text: zero.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 8 K. GRYGIEL, P. LESCANNE Proof. Since the number of closed binary λ-terms is not greater than the number ≥ of all binary terms of the same size, we conclude immediately that ρ ρ. 0 (cid:113) Let us now consider the functionals − − − 1 (cid:113)1 4z4(1 −zm + F) 1 z Φ (F) = , m 2z2 − − 1 1 4z4( −1 + F) 1 z Φ∞(F) = . 2z2 In particular, when m = 0, we have √ − 1 1 + 4z4F Φ (F) = . 0 2z2 We have also S S (z) = Φ ( (z)). m m m+1 The Φ ’s and Φ∞ are increasing over functions over [0, 1), which means that m ≤ ⇒ ≤ F G Φ (F) Φ (G), m m ≤ ⇒ ≤ F G Φ∞(F) (cid:101)Φ∞(G). (cid:101) ∈ N S For each m , let us consider the function (z) deﬁned as the ﬁxed point of m S Φm. In other words, m(z) is(cid:101)deﬁned as the so(cid:101)lution of the following equation: S S (z) = Φ ( (z)). m m m ≤ ≤ S ≤ S ≤ Notice that since S S S∞ we can claim that (z) (z) S m,n m+1,n ,n m m+1 ∞(z). Therefore, we have S(cid:101) ≤ S (5) Φ ( (z)) (z), m m m S ≤ S ≤ S (6) (cid:101) m(z) m(z) ∞(z). S (cid:114) Since (z) satisﬁes (cid:16) (cid:17) m (cid:101) (cid:101) − S − − 1 zm S 2z2 (z) = 1 1 4z4 − + (z) , m 1 z m we get (cid:101) (cid:101) − S − − S z2(1 zm) z2 2 (z) (1 z2)2 (z) + − = 0. m m 1 z ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: K.

text: GRYGIEL,

text: P.

text: LESCANNE

text: Proof.

text: Since

text: the

text: number

text: of

text: closed

text: binary

text: λ-terms

text: is

text: not

text: greater

text: than

text: the

text: number

text: of

text: all

text: binary

text: terms

text: of

text: the

text: same

text: size,

text: we

text: conclude

text: immediately

text: that

text: ρ

text: ρ.

text: Let

text: us

text: now

text: consider

text: the

text: functionals

text: −zm

text: F)

text: z

text: Φ

text: (F)

text: m

text: −1

text: F)

text: z

text: Φ∞(F)

text: In

text: particular,

text: when

text: m

text: we

text: have

text: Φ

text: (F)

text: We

text: have

text: also

text: S

text: S

text: (z)

text: Φ

text: (z)).

text: m

text: m

text: The

text: Φ

text: ’s

text: and

text: Φ∞

text: are

text: increasing

text: over

text: functions

text: over

text: which

text: means

text: that

text: m

text: F

text: G

text: Φ

text: (F)

text: Φ

text: (G),

text: m

text: m

text: F

text: G

text: Φ∞(F)

text: N

text: S

text: For

text: each

text: m

text: let

text: us

text: consider

text: the

text: function

text: (z)

text: deﬁned

text: as

text: the

text: ﬁxed

text: point

text: of

text: m

text: S

text: Φm.

text: In

text: other

text: words,

text: m(z)

text: as

text: the

text: of

text: the

text: following

text: equation:

text: S

text: S

text: (z)

text: Φ

text: (z)).

text: m

text: m

text: m

text: S

text: S

text: Notice

text: that

text: since

text: S

text: S

text: S∞

text: we

text: can

text: claim

text: that

text: (z)

text: (z)

text: S

text: m,n

text: ,n

text: m

text: ∞(z).

text: Therefore,

text: we

text: have

text: S

text: Φ

text: (z))

text: (z),

text: m

text: m

text: m

text: S

text: S

text: S

text: m(z)

text: m(z)

text: ∞(z).

text: S

text: Since

text: (z)

text: satisﬁes

text: m

text: S

text: zm

text: S

text: (z)

text: (z)

text: m

text: z

text: m

text: we

text: get

text: S

text: S

text: zm)

text: (z)

text: (z)

text: m

text: m

text: z

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 12 the dominant non-Gaussian errors for a wide range of 104 Sub survey volumes and is encapsulated in a single response Small function that correlates all modes in the spectrum. These T0+SSC (HM) results are relevant for the analysis of weak lensing sur- 103 T0 (HM) veys where the global mean is deﬁned by cosmological parameters. For power spectra referenced to the survey or local 102 mean, relevant for galaxy surveys where the mean density of tracers is typically estimated from the survey itself, the 1 - SSC eﬀect is a comparable eﬀect to other non-Gaussian GC ii 10 errors. Here our calibration is still in good agreement: C/ii better than the 10% level even when the non-Gaussian variance is a factor of 103 larger than the Gaussian vari- 1 ance. We have also shown that the stochasticity of the re- sponse from volume to volume is small. Hence to ﬁrst approximation, these eﬀects can be considered as an ex- 0.1 tra form of signal rather than noise. The unknown den- z=0 sity ﬂuctuation δ from super-survey modes can be con- Halo Model Variance b sidered as a parameter that in the observed power spec- 10-2 0.1 1 trum which can be ﬁt for with the response template. k [h/Mpc] We have demonstrated that this should be an excellent approximation in the quasilinear regime where the eﬀect of dilation can bias precision measurements of BAO fea- FIG. 11. Halo model for variance in excess over the Gaussian tures in the power spectrum. expectation CG at z = 0. While the SSC contribution is well ii Agreement with the halo model for the power spec- captured, the halo model overpredicts the variance of the small trum background response is also good implying that a box simulations by up to a factor of 3. halo model description may allow for eﬃcient extensions to alternate cosmologies. In fact our separate universe ulations by up to a factor of 3. Note that very rare halos analysis can also be used to calibrate the elements of contribute substantially to this term and that the ingre- the halo model and potentially improve agreement for dients of the halo model have not been as thoroughly other non-Gaussian terms. A crucial element of the halo tested in this regime. On the other hand, the halo model model is that halo bias is consistent with the mass func- for the SSC response term agrees nearly as well as the tion in the peak-background construction. Thus in prin- separate universe response calibration in the diﬀerence ciple halo bias can be calibrated from the response of the between the small and subbox results. halo mass function to a change in the background den- V. DISCUSSION sity [38]. We intend to study such applications of the separate universe simulations in a future work. In this paper we have employed separate universe sim- Acknowledgments.– We thank M. Becker, M. Busha, B. ulations to characterize accurately all SSC eﬀects from Erickson, G. Evrard, N. Gnedin, A. Kravtsov, D. Rudd, super-survey modes on matter power spectra measured R. Wechsler, and the University of Chicago Research from ﬁnite volume surveys. This approach automati- Computing Center for running, storing, and allowing us cally captures the separate eﬀects of beat coupling in the to use the large-volume simulations in this study. We quasilinear regime, halo sample variance in the nonlin- also thank M. Becker, D. Rudd., N. Gnedin, A. Kravtsov ear regime and a new dilation eﬀect which changes scales and F. Schmidt for useful discussions. YL and WH were in the power spectrum coherently across the survey vol- supported by U.S. Dept. of Energy contract DE-FG02- ume. It accurately quantiﬁes these eﬀects with a handful 13ER41958 and the Kavli Institute for Cosmological of small volume simulations once and for all, rather than Physics at the University of Chicago through grants the many thousands of survey speciﬁc volumes required NSF PHY-0114422 and NSF PHY-0551142. WH was in the direct quantiﬁcation. additionally supported by the David and Lucile Packard Agreement between the SSC model, where the eﬀect Foundation. MT was supported by World Premier In- is described as the response of the power spectrum to a ternational Research Center Initiative (WPI Initiative), change in the background density, and an extensive suite MEXT, Japan, by the FIRST program “Subaru Mea- of large volume simulations is excellent with no statisti- surements of Images and Redshifts (SuMIRe)”, CSTP, cally signiﬁcant deviations within the domain of validity Japan, and by Grant-in-Aid for Scientiﬁc Research from (cid:46) of the simulations k 3 h/Mpc for power spectra refer- the JSPS Promotion of Science (23340061). enced to the global mean. The SSC eﬀect here provides ##LTFigure##

text: the

text: dominant

text: non-Gaussian

text: errors

text: for

text: a

text: wide

text: range

text: of

font: default

text: Sub

text: survey

text: volumes

text: and

text: is

text: encapsulated

text: in

text: a

text: single

text: response

text: Small

text: function

text: that

text: correlates

text: all

text: modes

text: in

text: the

text: spectrum.

text: These

text: (HM)

text: results

text: are

text: relevant

text: for

text: the

text: analysis

text: of

text: weak

text: lensing

text: sur-

text: (HM)

text: veys

text: where

text: the

text: global

text: mean

text: is

text: deﬁned

text: by

text: cosmological

text: parameters.

text: For

text: power

text: spectra

text: referenced

text: to

text: the

text: survey

text: or

text: local

text: mean,

text: relevant

text: for

text: galaxy

text: surveys

text: where

text: the

text: mean

text: density

text: of

text: tracers

text: is

text: typically

text: estimated

text: from

text: the

text: survey

text: itself,

text: the

text: SSC

text: eﬀect

text: is

text: a

text: comparable

text: eﬀect

text: to

text: other

text: non-Gaussian

text: GC

text: ii

text: errors.

text: Here

text: our

text: calibration

text: is

text: still

text: in

text: good

text: agreement:

text: C/ii

text: better

text: than

text: the

text: level

text: even

text: when

text: the

text: non-Gaussian

text: variance

text: is

text: a

text: factor

text: of

text: larger

text: than

text: the

text: Gaussian

text: vari-

text: ance.

text: We

text: have

text: also

text: shown

text: that

text: the

text: stochasticity

text: of

text: the

text: re-

text: sponse

text: from

text: volume

text: to

text: volume

text: is

text: small.

text: Hence

text: to

text: ﬁrst

text: approximation,

text: these

text: eﬀects

text: can

text: be

text: considered

text: as

text: an

text: ex-

text: tra

text: form

text: of

text: signal

text: rather

text: than

text: noise.

text: The

text: unknown

text: den-

text: sity

text: ﬂuctuation

text: δ

text: from

text: super-survey

text: modes

text: can

text: be

text: con-

text: Halo

text: Model

text: Variance

text: b

text: sidered

text: as

text: a

text: parameter

text: that

text: in

text: the

text: observed

text: power

text: spec-

text: trum

text: which

text: can

text: be

text: ﬁt

text: for

text: with

text: the

text: response

text: template.

text: k

text: [h/Mpc]

text: We

text: have

text: demonstrated

text: that

text: this

text: should

text: be

text: an

text: excellent

text: approximation

text: in

text: the

text: quasilinear

text: regime

text: where

text: the

text: eﬀect

text: of

text: dilation

text: can

text: bias

text: precision

text: measurements

text: of

text: BAO

text: fea-

text: FIG.

text: Halo

text: model

text: for

text: variance

text: in

text: excess

text: over

text: the

text: Gaussian

text: tures

text: in

text: the

text: power

text: spectrum.

text: expectation

text: CG

text: at

text: z

text: While

text: the

text: SSC

text: contribution

text: is

text: well

text: ii

text: Agreement

text: with

text: the

text: halo

text: model

text: for

text: the

text: power

text: spec-

text: captured,

text: the

text: halo

text: model

text: overpredicts

text: the

text: variance

text: of

text: the

text: small

text: trum

text: background

text: response

text: is

text: also

text: good

text: implying

text: that

text: a

text: box

text: simulations

text: by

text: up

text: to

text: a

text: factor

text: of

text: halo

text: model

text: description

text: may

text: allow

text: for

text: eﬃcient

text: extensions

text: to

text: alternate

text: cosmologies.

text: In

text: fact

text: our

text: separate

text: universe

text: ulations

text: by

text: up

text: to

text: a

text: factor

text: of

text: Note

text: that

text: very

text: rare

text: halos

text: analysis

text: can

text: also

text: be

text: used

text: to

text: calibrate

text: the

text: elements

text: of

text: contribute

text: substantially

text: to

text: this

text: term

text: and

text: that

text: the

text: ingre-

text: the

text: halo

text: model

text: and

text: potentially

text: improve

text: agreement

text: for

text: dients

text: of

text: the

text: halo

text: model

text: have

text: not

text: been

text: as

text: thoroughly

text: other

text: non-Gaussian

text: terms.

text: A

text: crucial

text: element

text: of

text: the

text: halo

text: tested

text: in

text: this

text: regime.

text: On

text: the

text: other

text: hand,

text: the

text: halo

text: model

text: model

text: is

text: that

text: halo

text: bias

text: is

text: consistent

text: with

text: the

text: mass

text: func-

text: for

text: the

text: SSC

text: response

text: term

text: agrees

text: nearly

text: as

text: well

text: as

text: the

text: tion

text: in

text: the

text: peak-background

text: construction.

text: Thus

text: in

text: prin-

text: separate

text: universe

text: response

text: calibration

text: in

text: the

text: diﬀerence

text: ciple

text: halo

text: bias

text: can

text: be

text: calibrated

text: from

text: the

text: response

text: of

text: the

text: between

text: the

text: small

text: and

text: subbox

text: results.

text: halo

text: mass

text: function

text: to

text: a

text: change

text: in

text: the

text: background

text: den-

text: V.

text: DISCUSSION

text: sity

text: We

text: intend

text: to

text: study

text: such

text: applications

text: of

text: the

text: separate

text: universe

text: simulations

text: in

text: a

text: future

text: work.

text: In

text: this

text: paper

text: we

text: have

text: employed

text: separate

text: universe

text: sim-

text: Acknowledgments.–

text: We

text: thank

text: M.

text: Becker,

text: M.

text: Busha,

text: B.

text: ulations

text: to

text: characterize

text: accurately

text: all

text: SSC

text: eﬀects

text: from

text: Erickson,

text: G.

text: Evrard,

text: N.

text: Gnedin,

text: A.

text: Kravtsov,

text: D.

text: Rudd,

text: super-survey

text: modes

text: on

text: matter

text: power

text: spectra

text: measured

text: R.

text: Wechsler,

text: and

text: the

text: University

text: of

text: Chicago

text: Research

text: from

text: ﬁnite

text: volume

text: surveys.

text: This

text: approach

text: automati-

text: Computing

text: Center

text: for

text: running,

text: storing,

text: and

text: allowing

text: us

text: cally

text: captures

text: the

text: separate

text: eﬀects

text: of

text: beat

text: coupling

text: in

text: the

text: to

text: use

text: the

text: large-volume

text: simulations

text: in

text: this

text: study.

text: We

text: quasilinear

text: regime,

text: halo

text: sample

text: variance

text: in

text: the

text: nonlin-

text: also

text: thank

text: M.

text: Becker,

text: D.

text: Rudd.,

text: N.

text: Gnedin,

text: A.

text: Kravtsov

text: ear

text: regime

text: and

text: a

text: new

text: dilation

text: eﬀect

text: which

text: changes

text: scales

text: and

text: F.

text: Schmidt

text: for

text: useful

text: discussions.

text: YL

text: and

text: WH

text: were

text: in

text: the

text: power

text: spectrum

text: coherently

text: across

text: the

text: survey

text: vol-

text: supported

text: by

text: U.S.

text: Dept.

text: of

text: Energy

text: contract

text: ume.

text: It

text: accurately

text: quantiﬁes

text: these

text: eﬀects

text: with

text: a

text: handful

text: and

text: the

text: Kavli

text: Institute

text: for

text: Cosmological

text: of

text: small

text: volume

text: simulations

text: once

text: and

text: for

text: all,

text: rather

text: than

text: Physics

text: at

text: the

text: University

text: of

text: Chicago

text: through

text: grants

text: the

text: many

text: thousands

text: of

text: survey

text: speciﬁc

text: volumes

text: required

text: NSF

text: and

text: NSF

text: WH

text: was

text: in

text: the

text: direct

text: quantiﬁcation.

text: additionally

text: supported

text: by

text: the

text: David

text: and

text: Lucile

text: Packard

text: Agreement

text: between

text: the

text: SSC

text: model,

text: where

text: the

text: eﬀect

text: Foundation.

text: MT

text: was

text: supported

text: by

text: World

text: Premier

text: In-

text: is

text: described

text: as

text: the

text: response

text: of

text: the

text: power

text: spectrum

text: to

text: a

text: ternational

text: Research

text: Center

text: Initiative

text: (WPI

text: Initiative),

text: change

text: in

text: the

text: background

text: density,

text: and

text: an

text: extensive

text: suite

text: MEXT,

text: Japan,

text: by

text: the

text: FIRST

text: program

text: “Subaru

text: Mea-

text: of

text: large

text: volume

text: simulations

text: is

text: excellent

text: with

text: no

text: statisti-

text: surements

text: of

text: Images

text: and

text: Redshifts

text: (SuMIRe)”,

text: CSTP,

text: cally

text: signiﬁcant

text: deviations

text: within

text: the

text: domain

text: of

text: validity

text: Japan,

text: and

text: by

text: Grant-in-Aid

text: for

text: Scientiﬁc

text: Research

text: from

text: of

text: the

text: simulations

text: k

text: h/Mpc

text: for

text: power

text: spectra

text: refer-

text: the

text: JSPS

text: Promotion

text: of

text: Science

text: enced

text: to

text: the

text: global

text: mean.

text: The

text: SSC

text: eﬀect

text: here

text: provides

text: ##LTFigure##


text: → ∗ − Semileptonic decays B+ D( )(l+ν , l+l , νν¯) in the perturbative c (s) l QCD approach ∗ Wen-Fei Wang1 , Xin Yu1, Cai-Dian Lu¨1, and Zhen-Jun Xiao2 1 Center for Future High Energy Physics, Institute of High Energy Physics, Chinese Academy of Sciences, Beijing 100049, People’s Republic of China, 2 Department of Physics and Institute of Theoretical Physics, Nanjing Normal University, Nanjing, Jiangsu 210023, People’s Republic of China (Dated: May 26, 2020) Abstract → ∗ − In this paper we study the semileptonic decays of B+ D( )(l+ν , l+l , νν¯) (here l stands → ∗ c (s) l for e, µ, or τ). After evaluating the B+ (D , D ) transition form factors F (q2) and c (s) (s) 0,+,T V (q2), A (q2), T (q2) by employing the perturbative QCD factorization approach, we calculate 0,1,2 1,2,3 → the branching ratios for all these semileptonic decays. Our predictions for the values of the B+ → ∗ c D and B+ D transition form factors are consistent with those obtained by using other (s) c (s) methods. The branching ratios of the decay modes with ν¯ν are almost an order of magnitude larger − than the corresponding decays with l+l after the summation over the three neutrino generations. → The branching ratios for the decays with b d transitions are much smaller than those decays → with the b s transitions, due to the Cabibbo-Kobayashi-Maskawa suppression. We deﬁne ratios R and R ∗ for the branching ratios with the τ lepton versus µ, e lepton ﬁnal states to cancel the D D uncertainties of the form factors, which could possibly be tested in the near future. PACS numbers: 13.20.He, 12.38.Bx, 14.40.Nd ∗ wangwf@ihep.ac.cn 1 ##LTLine##

label: title

text: Semileptonic

text: decays

text: B+

text: D(

text: )(l+ν

text: l+l

text: νν¯)

text: in

text: the

text: perturbative

text: c

text: (s)

text: l

text: QCD

text: approach

label: author

text: Wen-Fei

text: Xin

text: Cai-Dian

text: and

text: Zhen-Jun

text: Center

text: for

text: Future

text: High

text: Energy

text: Physics,

text: Institute

text: of

text: High

text: Energy

text: Physics,

text: Chinese

text: Academy

text: of

text: Sciences,

text: Beijing

text: People’s

text: Republic

text: of

text: China,

text: Department

text: of

text: Physics

text: and

text: Institute

text: of

text: Theoretical

text: Physics,

text: Nanjing

text: Normal

text: University,

text: Nanjing,

text: Jiangsu

text: People’s

text: Republic

text: of

text: China

text: (Dated:

text: May

label: date

text: Abstract

label: abstract

text: In

text: this

text: paper

text: we

text: study

text: the

text: semileptonic

text: decays

text: of

text: B+

text: D(

text: )(l+ν

text: l+l

text: νν¯)

text: (here

text: l

text: stands

text: c

text: (s)

text: l

text: for

text: e,

text: µ,

text: or

text: τ).

text: After

text: evaluating

text: the

text: B+

text: (D

text: D

text: transition

text: form

text: factors

text: F

text: and

text: c

text: (s)

text: (s)

text: V

text: A

text: T

text: by

text: employing

text: the

text: perturbative

text: QCD

text: factorization

text: approach,

text: we

text: calculate

text: the

text: branching

text: ratios

text: for

text: all

text: these

text: semileptonic

text: decays.

text: Our

text: predictions

text: for

text: the

text: values

text: of

text: the

text: B+

text: c

text: D

text: and

text: B+

text: D

text: transition

text: form

text: factors

text: are

text: consistent

text: with

text: those

text: obtained

text: by

text: using

text: other

text: (s)

text: c

text: (s)

text: methods.

text: The

text: branching

text: ratios

text: of

text: the

text: decay

text: modes

text: with

text: ν¯ν

text: are

text: almost

text: an

text: order

text: of

text: magnitude

text: larger

text: than

text: the

text: corresponding

text: decays

text: with

text: l+l

text: after

text: the

text: summation

text: over

text: the

text: three

text: neutrino

text: generations.

text: The

text: branching

text: ratios

text: for

text: the

text: decays

text: with

text: b

text: d

text: transitions

text: are

text: much

text: smaller

text: than

text: those

text: decays

text: with

text: the

text: b

text: s

text: transitions,

text: due

text: to

text: the

text: Cabibbo-Kobayashi-Maskawa

text: suppression.

text: We

text: deﬁne

text: ratios

text: R

text: and

text: R

text: for

text: the

text: branching

text: ratios

text: with

text: the

text: τ

text: lepton

text: versus

text: µ,

text: e

text: lepton

text: ﬁnal

text: states

text: to

text: cancel

text: the

text: D

text: D

text: uncertainties

text: of

text: the

text: form

text: factors,

text: which

text: could

text: possibly

text: be

text: tested

text: in

text: the

text: near

text: future.

text: PACS

text: numbers:

text: wangwf@ihep.ac.cn

text: ##LTLine##


text: V (q2), A (q2), T (q2) in the pQCD factorization approach based on k factorization. 0,1,2 1,2,3 → → ∗ T The pQCD predictions for the values of the B D and B D transition form c (s) c (s) factors agree with those obtained using other methods. Utilizing these form factors, we → ∗ − calculated the branching ratios for all the semileptonic decays of B+ D( )(l+ν , l+l , νν¯). c (s) l Because of phase space suppression, the production ratios of the decay modes with lepton τ in the ﬁnal product are smaller than the corresponding decays with electron or muon in the ﬁnal product. The branching ratios of the decay modes with ν¯ν are almost an order − magnitude larger than the corresponding decays with l+l after the summation over the → three neutrino generations. The branching ratios for the decays with the b d transition → are much smaller than those with the b s transitions. In order to reduce the theoretical uncertainty of the pQCD predictions, we deﬁned two ratios R and R ∗ among the branching ratios for the the charged-current processes. The D D pQCD predictions are − → − Br(B D¯0τ ν¯ ) ≈ RD = Br(Bc− → D¯0l−ντ) 0.7 , (37) −c → ∗ − l Br(B D¯ 0τ ν¯ ) ≈ RD∗ = Br(Bc− → D¯∗0l−ντ) 0.6 , (38) c l with l = (e, µ). It would possible to test these predictions by LHCb and the forthcoming Super-B experiments. Acknowledgments This work is supported in part by the National Natural Science Foundation of China under Grant No. 11375208, 11228512, and 11235005. [1] I.P. Gouz, V.V. Kiselev, A.K. Likhoded, V.I. Romanovsky, and O.P. Yushchenko, Phys. At. Nucl. 67, 1559 (2004). [2] N. Brambilla et al., (Quarkonium Working Group), Report No. CERN-2005-005; M.P. Altarelli and F. Teubert, Int. J. Mod. Phys. A 23, 5117 (2008). [3] R. Dhir and R.C. Verma, Phys. Scr. 82, 065101 (2010). [4] A. Faessler, Th. Gutsche, M.A. Ivanov, J.G. K¨orner, and V.E. Lyubovitskij, Eur. Phys. J. direct C 4, 1 (2002). [5] C.Q. Geng, C.W. Hwang, and C.C. Liu, Phys. Rev. D 65, 094037 (2002). [6] D. Ebert, R.N. Faustov, and V.O. Galkin, Phys. Rev. D 82, 034032 (2010). [7] I. Ahmed, M. A. Paracha, M. Junaid, A. Ahmed, A. Rehman and M. J. Aslam, arXiv:1107.5694. [8] A. Ahmed, I. Ahmed, M. A. Paracha, M. Junaid, A. Rehman and M. J. Aslam, arXiv:1108.1058. [9] K. Azizi, F. Falahati, V. Bashiry, and S.M. Zebarjad, Phys. Rev. D 77, 114024 (2008). [10] K. Azizi and R. Khosravi, Phys. Rev. D 78, 036005 (2008). [11] T.W. Yeh and H.-n. Li, Phys. Rev. D 56, 1615 (1997); H.-n. Li and H.L. Yu, Phys. Rev. Lett. 74, 4388 (1995); Phys. Lett. B 353, 301 (1995); Phys. Rev. D 53, 2480 (1996). 12 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: V

text: A

text: T

text: in

text: the

text: pQCD

text: factorization

text: approach

text: based

text: on

text: k

text: factorization.

text: T

text: The

text: pQCD

text: predictions

text: for

text: the

text: values

text: of

text: the

text: B

text: D

text: and

text: B

text: D

text: transition

text: form

text: c

text: (s)

text: c

text: (s)

text: factors

text: agree

text: with

text: those

text: obtained

text: using

text: other

text: methods.

text: Utilizing

text: these

text: form

text: factors,

text: we

text: calculated

text: the

text: branching

text: ratios

text: for

text: all

text: the

text: semileptonic

text: decays

text: of

text: B+

text: D(

text: )(l+ν

text: l+l

text: νν¯).

text: c

text: (s)

text: l

text: Because

text: of

text: phase

text: space

text: suppression,

text: the

text: production

text: ratios

text: of

text: the

text: decay

text: modes

text: with

text: lepton

text: τ

text: in

text: the

text: ﬁnal

text: product

text: are

text: smaller

text: than

text: the

text: corresponding

text: decays

text: with

text: electron

text: or

text: muon

text: in

text: the

text: ﬁnal

text: product.

text: The

text: branching

text: ratios

text: of

text: the

text: decay

text: modes

text: with

text: ν¯ν

text: are

text: almost

text: an

text: order

text: magnitude

text: larger

text: than

text: the

text: corresponding

text: decays

text: with

text: l+l

text: after

text: the

text: summation

text: over

text: the

text: three

text: neutrino

text: generations.

text: The

text: branching

text: ratios

text: for

text: the

text: decays

text: with

text: the

text: b

text: d

text: transition

text: are

text: much

text: smaller

text: than

text: those

text: with

text: the

text: b

text: s

text: transitions.

text: In

text: order

text: to

text: reduce

text: the

text: theoretical

text: uncertainty

text: of

text: the

text: pQCD

text: predictions,

text: we

text: deﬁned

text: two

text: ratios

text: R

text: and

text: R

text: among

text: the

text: branching

text: ratios

text: for

text: the

text: the

text: charged-current

text: processes.

text: The

text: D

text: D

text: pQCD

text: predictions

text: are

text: Br(B

text: D¯0τ

text: ν¯

text: RD

text: Br(Bc−

text: D¯0l−ντ)

text: −c

text: l

text: Br(B

text: D¯

text: 0τ

text: ν¯

text: RD∗

text: Br(Bc−

text: D¯∗0l−ντ)

text: c

text: l

text: with

text: l

text: (e,

text: µ).

text: It

text: would

text: possible

text: to

text: test

text: these

text: predictions

text: by

text: LHCb

text: and

text: the

text: forthcoming

text: Super-B

text: experiments.

text: Acknowledgments

text: This

text: work

text: is

text: supported

text: in

text: part

text: by

text: the

text: National

text: Natural

text: Science

text: Foundation

text: of

text: China

text: under

text: Grant

text: No.

text: and

text: I.P.

text: Gouz,

text: V.V.

text: Kiselev,

text: A.K.

text: Likhoded,

text: V.I.

text: Romanovsky,

text: and

text: O.P.

text: Yushchenko,

text: Phys.

text: At.

text: Nucl.

text: N.

text: Brambilla

text: et

text: al.,

text: (Quarkonium

text: Working

text: Group),

text: Report

text: No.

text: M.P.

text: Altarelli

text: and

text: F.

text: Teubert,

text: Int.

text: J.

text: Mod.

text: Phys.

text: A

text: R.

text: Dhir

text: and

text: R.C.

text: Verma,

text: Phys.

text: Scr.

text: A.

text: Faessler,

text: Th.

text: Gutsche,

text: M.A.

text: Ivanov,

text: J.G.

text: K¨orner,

text: and

text: V.E.

text: Lyubovitskij,

text: Eur.

text: Phys.

text: J.

text: direct

text: C

text: C.Q.

text: Geng,

text: C.W.

text: Hwang,

text: and

text: C.C.

text: Liu,

text: Phys.

text: Rev.

text: D

text: D.

text: Ebert,

text: R.N.

text: Faustov,

text: and

text: V.O.

text: Galkin,

text: Phys.

text: Rev.

text: D

text: I.

text: Ahmed,

text: M.

text: A.

text: Paracha,

text: M.

text: Junaid,

text: A.

text: Ahmed,

text: A.

text: Rehman

text: and

text: M.

text: J.

text: Aslam,

text: A.

text: Ahmed,

text: I.

text: Ahmed,

text: M.

text: A.

text: Paracha,

text: M.

text: Junaid,

text: A.

text: Rehman

text: and

text: M.

text: J.

text: Aslam,

text: K.

text: Azizi,

text: F.

text: Falahati,

text: V.

text: Bashiry,

text: and

text: S.M.

text: Zebarjad,

text: Phys.

text: Rev.

text: D

text: K.

text: Azizi

text: and

text: R.

text: Khosravi,

text: Phys.

text: Rev.

text: D

text: T.W.

text: Yeh

text: and

text: H.-n.

text: Li,

text: Phys.

text: Rev.

text: D

text: H.-n.

text: Li

text: and

text: H.L.

text: Yu,

text: Phys.

text: Rev.

text: Lett.

text: Phys.

text: Lett.

text: B

text: Phys.

text: Rev.

text: D

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:90) In the last section we consider a similar case arising from the theory of elliptic equations: F H (Σ) := u (x)f(x) dx + λ 1(Σ), (3) Σ ⊂ (cid:26) Ω where Ω R2 is a given bounded open subset, f is a given L2(Ω) function, and u is the unique Σ solution of the PDE − \ ∆u = f in Ω Σ, ∪ u = 0 on ∂Ω Σ. One has to remark that while a lot of properties are known for minimizers of the average distance functional (see Buttazzo, Oudet, Stepanov, 2002, Buttazzo, Stepanov, 2003, Paolini, Stepanov 2004, Stepanov, 2006), like partial regularity, absence of loops, topological properties (ﬁnite number of branching points, each of which is a regular tripod), no such property has been studied for minimizers of (3). 2. The Euler equation for the average distance functional ⊂ ∈ For a compact set Σ Rn we denote by πΣ the projection map to Σ (i.e. such that πΣ(x) Σ is ∈ one of the nearest point in Σ to x Rn). This map is uniquely deﬁned everywhere except the ridge R ∈ set , which is deﬁned as the set of all x Rn for which the minimum distance to Σ is attained at Σ R more than one point. It is well known that is the set of non diﬀerentiability points of the distance ∈ (cid:55)→Σ function to Σ (that is, of the map x Rn dist (x, Σ)), and since the latter map is semiconcave, H − − this set is an ( n 1, n 1)-rectiﬁable Borel set (see Proposition 3.7 in Mantegazza, Mennucci, 2003). ⊂ ∈ We will denote b(cid:103)y B (x) Rn the open ball with radius r > 0 and center x Rn. The line r segment with endpoints A and B will be denoted by AB, the arc of a curve with the same endpoints will be denoted by AB (usually in this paper we will deal with arcs of circle). To be begin with, we estimate the ascending local slope of (2) deﬁned by F (cid:48) − F |F(cid:48)| ( (Σ ) (Σ))+ (Σ) := lim sup (cid:48) , (cid:48) → d (Σ , Σ) dH(Σ ,Σ) 0 H where d stands for Hausdorﬀ distance between sets. The following simple assertion is valid. H R |F(cid:48)| ≥ Proposition 2.1. If µ( ) = 0, one has (Σ) λ. Σ ∈ − { } Proof. Let x Σ be such that µ((πΣ) 1( x )) = 0 (all but a countable number of points of Σ have ∪ this property). Let then Σ := Σ I , where I stands for the line segment of length ε > 0, with one ε ε ε H H of the endpoints x and such that πΣ(I ) = x. Then d (Σ , Σ) = ε and 1(Σ ) = 1(Σ) + ε. On the ε H ε ε other hand, denoting (cid:90) { ∈ (cid:90) ≥ } G := z Rn : dist (z, Σ) dist (z, I ) , ε ε we have that ≥ (cid:90) dist (x, Σ) dµ(x) dist (x, Σ ) dµ(x) ε Rn Rn ≥ − dist (x, Σ) dµ(x) εµ(G ). ε Rn Thus F − F − |F(cid:48)| ≥ ( (Σ ) (Σ))+ ≥ (λε εµ(G ))+ ε ε (Σ) lim sup lim , dH(Σε,Σ)→0 dH(Σε, Σ) ε→0+ ε (cid:38) { } → (cid:3) and to conclude the proof it suﬃces to mind that µ(G ) = o(1), because G x as ε 0+. ε ε The above proposition in fact means that for the functional (2) no set Σ (not even a minimizer) is stationary in the strong sense, i.e. is such that F (cid:48) F (cid:48) (Σ ) = (Σ) + o(d (Σ, Σ )) H (cid:48) → as Σ Σ in Hausdorﬀ distance. Therefore, in search for the natural notion of stationary points of F → we have to restrict the set of admissible variations of Σ. For this purpose let φ : Rn Rn be a ε one parameter group of diﬀeomorphisms satisfying 2 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: In

text: the

text: last

text: section

text: we

text: consider

text: a

text: similar

text: case

text: arising

text: from

text: the

text: theory

text: of

text: elliptic

text: equations:

text: F

text: H

text: (Σ)

text: u

text: (x)f(x)

text: dx

text: λ

text: Σ

text: Ω

text: where

text: Ω

text: is

text: a

text: given

text: bounded

text: open

text: subset,

text: f

text: is

text: a

text: given

text: function,

text: and

text: u

text: is

text: the

text: unique

text: Σ

text: solution

text: of

text: the

text: PDE

text: ∆u

text: f

text: in

text: Ω

text: Σ,

text: u

text: on

text: ∂Ω

text: Σ.

text: One

text: has

text: to

text: remark

text: that

text: while

text: a

text: lot

text: of

text: properties

text: are

text: known

text: for

text: minimizers

text: of

text: the

text: average

text: distance

text: functional

text: (see

text: Buttazzo,

text: Oudet,

text: Stepanov,

text: Buttazzo,

text: Stepanov,

text: Paolini,

text: Stepanov

text: Stepanov,

text: like

text: partial

text: regularity,

text: absence

text: of

text: loops,

text: topological

text: properties

text: (ﬁnite

text: number

text: of

text: branching

text: points,

text: each

text: of

text: which

text: is

text: a

text: regular

text: tripod),

text: no

text: such

text: property

text: has

text: been

text: studied

text: for

text: minimizers

text: of

text: The

text: Euler

text: equation

text: for

text: the

text: average

text: distance

text: functional

text: For

text: a

text: compact

text: set

text: Σ

text: Rn

text: we

text: denote

text: by

text: πΣ

text: the

text: projection

text: map

text: to

text: Σ

text: (i.e.

text: such

text: that

text: πΣ(x)

text: Σ

text: is

text: one

text: of

text: the

text: nearest

text: point

text: in

text: Σ

text: to

text: x

text: Rn).

text: This

text: map

text: is

text: uniquely

text: deﬁned

text: everywhere

text: except

text: the

text: ridge

text: R

text: set

text: which

text: is

text: deﬁned

text: as

text: the

text: set

text: of

text: all

text: x

text: Rn

text: for

text: which

text: the

text: minimum

text: distance

text: to

text: Σ

text: is

text: attained

text: at

text: Σ

text: R

text: more

text: than

text: one

text: point.

text: It

text: is

text: well

text: known

text: that

text: is

text: the

text: set

text: of

text: non

text: diﬀerentiability

text: points

text: of

text: the

text: distance

text: function

text: to

text: Σ

text: (that

text: is,

text: of

text: the

text: map

text: x

text: Rn

text: dist

text: (x,

text: Σ)),

text: and

text: since

text: the

text: latter

text: map

text: is

text: semiconcave,

text: H

text: this

text: set

text: is

text: an

text: n

text: n

text: Borel

text: set

text: (see

text: Proposition

text: in

text: Mantegazza,

text: Mennucci,

text: We

text: will

text: denote

text: B

text: (x)

text: Rn

text: the

text: open

text: ball

text: with

text: radius

text: r

text: and

text: center

text: x

text: Rn.

text: The

text: line

text: r

text: segment

text: with

text: endpoints

text: A

text: and

text: B

text: will

text: be

text: denoted

text: by

text: AB,

text: the

text: arc

text: of

text: a

text: curve

text: with

text: the

text: same

text: endpoints

text: will

text: be

text: denoted

text: by

text: AB

text: (usually

text: in

text: this

text: paper

text: we

text: will

text: deal

text: with

text: arcs

text: of

text: circle).

text: To

text: be

text: begin

text: with,

text: we

text: estimate

text: the

text: ascending

text: local

text: slope

text: of

text: deﬁned

text: by

text: F

text: F

text: (Σ

text: (Σ))+

text: (Σ)

text: lim

text: sup

text: d

text: (Σ

text: Σ)

text: dH(Σ

text: ,Σ)

text: H

text: where

text: d

text: stands

text: for

text: Hausdorﬀ

text: distance

text: between

text: sets.

text: The

text: following

text: simple

text: assertion

text: is

text: valid.

text: H

text: R

text: Proposition

text: If

text: µ(

text: one

text: has

text: (Σ)

text: λ.

text: Σ

text: Proof.

text: Let

text: x

text: Σ

text: be

text: such

text: that

text: µ((πΣ)

text: x

text: (all

text: but

text: a

text: countable

text: number

text: of

text: points

text: of

text: Σ

text: have

text: this

text: property).

text: Let

text: then

text: Σ

text: Σ

text: I

text: where

text: I

text: stands

text: for

text: the

text: line

text: segment

text: of

text: length

text: ε

text: with

text: one

text: ε

text: ε

text: ε

text: H

text: H

text: of

text: the

text: endpoints

text: x

text: and

text: such

text: that

text: πΣ(I

text: x.

text: Then

text: d

text: (Σ

text: Σ)

text: ε

text: and

text: ε.

text: On

text: the

text: ε

text: H

text: ε

text: ε

text: other

text: hand,

text: denoting

text: G

text: z

text: Rn

text: dist

text: (z,

text: Σ)

text: dist

text: (z,

text: I

text: ε

text: ε

text: we

text: have

text: that

text: dist

text: (x,

text: Σ)

text: dµ(x)

text: dist

text: (x,

text: Σ

text: dµ(x)

text: ε

text: Rn

text: Rn

text: dist

text: (x,

text: Σ)

text: dµ(x)

text: εµ(G

text: ε

text: Rn

text: Thus

text: F

text: F

text: (Σ

text: (Σ))+

text: (λε

text: εµ(G

text: ε

text: ε

text: (Σ)

text: lim

text: sup

text: lim

text: dH(Σε,

text: Σ)

text: ε→0+

text: ε

text: and

text: to

text: conclude

text: the

text: proof

text: it

text: suﬃces

text: to

text: mind

text: that

text: µ(G

text: because

text: G

text: x

text: as

text: ε

text: ε

text: ε

text: The

text: above

text: proposition

text: in

text: fact

text: means

text: that

text: for

text: the

text: functional

text: no

text: set

text: Σ

text: (not

text: even

text: a

text: minimizer)

text: is

text: stationary

text: in

text: the

text: strong

text: sense,

text: i.e.

text: is

text: such

text: that

text: F

text: F

text: (Σ

text: (Σ)

text: o(d

text: (Σ,

text: Σ

text: H

text: as

text: Σ

text: Σ

text: in

text: Hausdorﬀ

text: distance.

text: Therefore,

text: in

text: search

text: for

text: the

text: natural

text: notion

text: of

text: stationary

text: points

text: of

text: F

text: we

text: have

text: to

text: restrict

text: the

text: set

text: of

text: admissible

text: variations

text: of

text: Σ.

text: For

text: this

text: purpose

text: let

text: φ

text: Rn

text: Rn

text: be

text: a

text: ε

text: one

text: parameter

text: group

text: of

text: diﬀeomorphisms

text: satisfying

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Clearly, every stationary point depends on the problem data, which in this case is the measure µ. To emphasize this dependence, we will further sometimes say for stationary points for the functional F that they are stationary with respect to µ. In the most important particular case we will be ⊂ L ⊂ interested in µ is a uniform measure over some open Ω Rn (i.e. µ = n Ω) with Σ Ω. In such a situation we will be speaking of stationary points with respect to the set Ω. 3. Examples of regular stationary points We will ﬁrst show that, in sharp contrast with minimizers, stationary points may contain closed loops (i.e. homeomorphic images of S1). L Proposition 3.1. Let µ := 2 B (0). There exist r < 1 such that the circumference ∂B (0) is a 1 r stationary point for functional (2) if and only if λ < 1. Nevertheless, no circumference is a minimizer 2 of (2), since minimizers cannot contain closed loops. Proof. We set Σ := ∂B (0) and impose (6). We choose X to be normal to Σ without loss of generality, r since the normal part only plays a role in (6). If we write the integral term in polar coordinates, the \ integrand depends(cid:90)on(cid:28)ly on the angle. Setting(cid:29)A = B (0(cid:90)) and B = B (0) B (0), and letting ν(x) be r 1 r the outward unit normal to ∂B (0), we get r − πΣ(x) x (cid:90) (cid:104) (cid:105) X(πΣ(x)), | − | dx = X(πΣ(x)), ν(πΣ(x)) dx πΣ(x) x Ω A − (cid:104) (cid:105) X(πΣ(x)), ν(πΣ(x)) dx, (cid:90) (cid:90)B (cid:90) and we can compute (cid:104) (cid:105) r (cid:90) 2π | | X(πΣ(x)), ν(πΣ(x)) dx = X(θ) ρ dρdθ A 0 0 1 2π | | = r2 X(θ) dθ, (cid:90) 2 0 (cid:90) and similarly for the integral over B. Moreover, (cid:104) (cid:105) − | |(cid:104) (cid:105) H −1 2π | | X, H = H (x) X(x), ν(x) d 1(x) = X(θ) rdθ. Σ Σ r ∂Br(0) 0 (cid:18) (cid:19) (cid:90) So the Euler equation reads r2 − 1 + λ 2π |X(θ)|dθ = 0. (cid:112) (9) 2 0 − This equation is identically satisﬁed, if and only if λ < 1/2, for r = 1/2 λ (of course, λ = 1/2 would also suite for (9), but it corresponds to a degenerate case when the circumference reduces to a point). To show that minimizers of (2) cannot contain closed loops, and hence the above stationary points are not minimizers, we may act as in the proof of absence of loops in minimizers of average distance functionals with length constraint (see e.g. Paolini, Stepanov, 2004, Buttazzo, Oudet, Stepanov 2002 or Buttazzo, Stepanov, 2003). In fact, suppose that Σ is a minimizer containing a closed loop. Then ⊂ ∈ there is a set of positive length C Σ such that for every x C and for every ε > 0 there is a closed ⊂ ∈ H ≥ \ connected subset D Σ such that x D , diam D = ε (hence 1(D ) ε) and Σ := Σ D ε ε ε − ε { } ε ∈ ε is connected. We may suppose without loss of generality that µ((πΣ) 1( x )) = 0 for all x C (cid:90) (cid:90) (since the set of atoms of the latter measure is clearly at most countable). One has then by triangle inequality ≤ − dist (x, Σ ) dµ(x) dist (x, Σ) dµ(x) + εµ((πΣ) 1(D )), ε ε Rn Rn 5 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Clearly,

text: every

text: stationary

text: point

text: depends

text: on

text: the

text: problem

text: data,

text: which

text: in

text: this

text: case

text: is

text: the

text: measure

text: µ.

text: To

text: emphasize

text: this

text: dependence,

text: we

text: will

text: further

text: sometimes

text: say

text: for

text: stationary

text: points

text: for

text: the

text: functional

text: F

text: that

text: they

text: are

text: stationary

text: with

text: respect

text: to

text: µ.

text: In

text: the

text: most

text: important

text: particular

text: case

text: we

text: will

text: be

text: L

text: interested

text: in

text: µ

text: is

text: a

text: uniform

text: measure

text: over

text: some

text: open

text: Ω

text: Rn

text: (i.e.

text: µ

text: n

text: Ω)

text: with

text: Σ

text: Ω.

text: In

text: such

text: a

text: situation

text: we

text: will

text: be

text: speaking

text: of

text: stationary

text: points

text: with

text: respect

text: to

text: the

text: set

text: Ω.

label: section

text: Examples

text: of

text: regular

text: stationary

text: points

text: We

text: will

text: ﬁrst

text: show

text: that,

text: in

text: sharp

text: contrast

text: with

text: minimizers,

text: stationary

text: points

text: may

text: contain

text: closed

text: loops

text: (i.e.

text: homeomorphic

text: images

text: of

text: L

text: Proposition

text: Let

text: µ

text: B

text: There

text: exist

text: r

text: such

text: that

text: the

text: circumference

text: ∂B

text: is

text: a

text: r

text: stationary

text: point

text: for

text: functional

text: if

text: and

text: only

text: if

text: λ

text: Nevertheless,

text: no

text: circumference

text: is

text: a

text: minimizer

text: of

text: since

text: minimizers

text: cannot

text: contain

text: closed

text: loops.

text: Proof.

text: We

text: set

text: Σ

text: ∂B

text: and

text: impose

text: We

text: choose

text: X

text: to

text: be

text: normal

text: to

text: Σ

text: without

text: loss

text: of

text: generality,

text: r

text: since

text: the

text: normal

text: part

text: only

text: plays

text: a

text: role

text: in

text: If

text: we

text: write

text: the

text: integral

text: term

text: in

text: polar

text: coordinates,

text: the

text: integrand

text: on

text: the

text: angle.

text: B

text: and

text: B

text: B

text: B

text: and

text: letting

text: ν(x)

text: be

text: r

text: r

text: the

text: outward

text: unit

text: normal

text: to

text: ∂B

text: we

text: get

text: r

text: πΣ(x)

text: x

text: X(πΣ(x)),

text: dx

text: X(πΣ(x)),

text: ν(πΣ(x))

text: dx

text: πΣ(x)

text: x

text: Ω

text: A

text: X(πΣ(x)),

text: ν(πΣ(x))

text: dx,

text: and

text: we

text: can

text: compute

text: r

text: 2π

text: X(πΣ(x)),

text: ν(πΣ(x))

text: dx

text: X(θ)

text: ρ

text: dρdθ

text: A

text: 2π

text: X(θ)

text: dθ,

text: and

text: similarly

text: for

text: the

text: integral

text: over

text: B.

text: Moreover,

text: H

text: −1

text: 2π

text: X,

text: H

text: H

text: (x)

text: X(x),

text: ν(x)

text: d

text: X(θ)

text: rdθ.

text: Σ

text: Σ

text: r

text: So

text: the

text: Euler

text: equation

text: reads

text: λ

text: 2π

text: |X(θ)|dθ

text: This

text: equation

text: is

text: identically

text: satisﬁed,

text: if

text: and

text: only

text: if

text: λ

text: for

text: r

text: λ

text: (of

text: course,

text: λ

text: would

text: also

text: suite

text: for

text: but

text: it

text: corresponds

text: to

text: a

text: degenerate

text: case

text: when

text: the

text: circumference

text: reduces

text: to

text: a

text: point).

text: To

text: show

text: that

text: minimizers

text: of

text: cannot

text: contain

text: closed

text: loops,

text: and

text: hence

text: the

text: above

text: stationary

text: points

text: are

text: not

text: minimizers,

text: we

text: may

text: act

text: as

text: in

text: the

text: proof

text: of

text: absence

text: of

text: loops

text: in

text: minimizers

text: of

text: average

text: distance

text: functionals

text: with

text: length

text: constraint

text: (see

text: e.g.

text: Paolini,

text: Stepanov,

text: Buttazzo,

text: Oudet,

text: Stepanov

text: or

text: Buttazzo,

text: Stepanov,

text: In

text: fact,

text: suppose

text: that

text: Σ

text: is

text: a

text: minimizer

text: containing

text: a

text: closed

text: loop.

text: Then

text: there

text: is

text: a

text: set

text: of

text: positive

text: length

text: C

text: Σ

text: such

text: that

text: for

text: every

text: x

text: C

text: and

text: for

text: every

text: ε

text: there

text: is

text: a

text: closed

text: H

text: connected

text: subset

text: D

text: Σ

text: such

text: that

text: x

text: D

text: diam

text: D

text: ε

text: (hence

text: ε)

text: and

text: Σ

text: Σ

text: D

text: ε

text: ε

text: ε

text: ε

text: ε

text: ε

text: is

text: connected.

text: We

text: may

text: suppose

text: without

text: loss

text: of

text: generality

text: that

text: µ((πΣ)

text: x

text: for

text: all

text: x

text: C

text: (since

text: the

text: set

text: of

text: atoms

text: of

text: the

text: latter

text: measure

text: is

text: clearly

text: at

text: most

text: countable).

text: One

text: has

text: then

text: by

text: triangle

text: inequality

text: dist

text: (x,

text: Σ

text: dµ(x)

text: dist

text: (x,

text: Σ)

text: dµ(x)

text: εµ((πΣ)

text: ε

text: ε

text: Rn

text: Rn

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: EQUIVARIANT LATTICE GENERATORS AND MARKOV BASES 17 Remark 4.10. The maximal degree of the generators in Theorem 4.7 matches the degrees in Table 1 of [HdC13]. However, we stop short of proving that our generating set is an equivariant Gro¨bner basis and we doubt that there needs to exist a term order for which it is one. According to our experiments in truncations, we expect the degrees in Gro¨bner bases to exceed those in Theorem 4.7. For instance in width ﬁve for a = 2, b = 1, the Markov complexity in Theorem 4.7 is three, while among many thousand random weight orders we have not found one with complexity smaller than ﬁve. In fact, we don’t even know if kernels of the form considered here always admit ﬁnite equivariant Gro¨bner bases. 5. Conclusion The main result of [DEKL13] is that once the parameters of the single monomial map are ﬁxed (e.g., the exponents a, b in the case of width 2), there exists a ﬁnite equivariant Markov basis. Precisely, the ﬁniteness means that the description of a Markov basis for a truncated problem does not depend on the width of truncation, which can be viewed as another parameter “tending to inﬁnity”. One striking example of a family of toric maps where Noetherianity of equivariant kernels fails appears in De Loera and Onn’s no hope theorem [DO06]: Markov bases for three-way contingency tables become arbitrarily complicated: the number of diﬀerent orbits as well as the degrees of their elements diverge as the sizes of the tables tend to inﬁnity. Our work settles problems (L1) and (M1) in width two via explicit constructions of equivariant lattice and Markov bases, respectively. The sharp width bounds that follow, answering (BL1) and (BM1) in width two, are linear functions of the width of the monomial map and of its exponents, respectively. The more general questions (L2) and (M2) remain open, and already the combinatorics of (M1) in width larger than two appears to be a lot more complicated than that in the case of width two. Nonetheless, the very modest bounds on the width in the settled cases shall fuel optimism as to practical computation of up-to-symmetry generators of kernels of equivariant toric maps in applications. References [4ti2] 4ti2 team, 4ti2—a software package for algebraic, geometric and combinatorial problems on linear spaces, available at www.4ti2.de. [AH07] Matthias Aschenbrenner and Christopher J. Hillar, Finite generation of symmetric ideals, Trans. Amer. Math. Soc. 359 (2007), 5171–5192. [AH09] , Erratum for “Finite generation of symmetric ideals”, Trans. Amer. Math. Soc. 361 (2009), 5627. [AT05] Satoshi Aoki and Akimichi Takemura, Markov chain Monte Carlo exact tests for incomplete two-way contingency table, Journal of Statistical Computation and Simulation 75 (2005), no. 10, 787–812. [DEKL13] Jan Draisma, Rob H. Eggermont, Robert Krone, and Anton Leykin, Noetherianity for inﬁnite-dimensional toric varieties, preprint, arXiv: 1306.0828 (2013). ##LTLine##

text: EQUIVARIANT

text: LATTICE

text: GENERATORS

text: AND

text: MARKOV

text: BASES

text: Remark

text: The

text: maximal

text: degree

text: of

text: the

text: generators

text: in

text: Theorem

text: matches

text: the

text: degrees

text: in

text: Table

text: of

text: However,

text: we

text: stop

text: short

text: of

text: proving

text: that

text: our

text: generating

text: set

text: is

text: an

text: equivariant

text: Gro¨bner

text: basis

text: and

text: we

text: doubt

text: that

text: there

text: needs

text: to

text: exist

text: a

text: term

text: order

text: for

text: which

text: it

text: is

text: one.

text: According

text: to

text: our

text: experiments

text: in

text: truncations,

text: we

text: expect

text: the

text: degrees

text: in

text: Gro¨bner

text: bases

text: to

text: exceed

text: those

text: in

text: Theorem

text: For

text: instance

text: in

text: width

text: ﬁve

text: for

text: a

text: b

text: the

text: Markov

text: complexity

text: in

text: Theorem

text: is

text: three,

text: while

text: among

text: many

text: thousand

text: random

text: weight

text: orders

text: we

text: have

text: not

text: found

text: one

text: with

text: complexity

text: smaller

text: than

text: ﬁve.

text: In

text: fact,

text: we

text: don’t

text: even

text: know

text: if

text: kernels

text: of

text: the

text: form

text: considered

text: here

text: always

text: admit

text: ﬁnite

text: equivariant

text: Gro¨bner

text: bases.

text: Conclusion

text: The

text: main

text: result

text: of

text: is

text: that

text: once

text: the

text: parameters

text: of

text: the

text: single

text: monomial

text: map

text: are

text: ﬁxed

text: (e.g.,

text: the

text: exponents

text: a,

text: b

text: in

text: the

text: case

text: of

text: width

text: there

text: exists

text: a

text: ﬁnite

text: equivariant

text: Markov

text: basis.

text: Precisely,

text: the

text: ﬁniteness

text: means

text: that

text: the

text: description

text: of

text: a

text: Markov

text: basis

text: for

text: a

text: truncated

text: problem

text: does

text: not

text: depend

text: on

text: the

text: width

text: of

text: truncation,

text: which

text: can

text: be

text: viewed

text: as

text: another

text: parameter

text: “tending

text: to

text: inﬁnity”.

text: One

text: striking

text: example

text: of

text: a

text: family

text: of

text: toric

text: maps

text: where

text: Noetherianity

text: of

text: equivariant

text: kernels

text: fails

text: appears

text: in

text: De

text: Loera

text: and

text: Onn’s

text: no

text: hope

text: theorem

text: Markov

text: bases

text: for

text: three-way

text: contingency

text: tables

text: become

text: arbitrarily

text: complicated:

text: the

text: number

text: of

text: diﬀerent

text: orbits

text: as

text: well

text: as

text: the

text: degrees

text: of

text: their

text: elements

text: diverge

text: as

text: the

text: sizes

text: of

text: the

text: tables

text: tend

text: to

text: inﬁnity.

text: Our

text: work

text: settles

text: problems

text: and

text: in

text: width

text: two

text: via

text: explicit

text: constructions

text: of

text: equivariant

text: lattice

text: and

text: Markov

text: bases,

text: respectively.

text: The

text: sharp

text: width

text: bounds

text: that

text: follow,

text: answering

text: and

text: in

text: width

text: two,

text: are

text: linear

text: functions

text: of

text: the

text: width

text: of

text: the

text: monomial

text: map

text: and

text: of

text: its

text: exponents,

text: respectively.

text: The

text: more

text: general

text: questions

text: and

text: remain

text: open,

text: and

text: already

text: the

text: combinatorics

text: of

text: in

text: width

text: larger

text: than

text: two

text: appears

text: to

text: be

text: a

text: lot

text: more

text: complicated

text: than

text: that

text: in

text: the

text: case

text: of

text: width

text: two.

text: Nonetheless,

text: the

text: very

text: modest

text: bounds

text: on

text: the

text: width

text: in

text: the

text: settled

text: cases

text: shall

text: fuel

text: optimism

text: as

text: to

text: practical

text: computation

text: of

text: up-to-symmetry

text: generators

text: of

text: kernels

text: of

text: equivariant

text: toric

text: maps

text: in

text: applications.

text: References

text: team,

text: software

text: package

text: for

text: algebraic,

text: geometric

text: and

text: combinatorial

text: problems

text: on

text: linear

text: spaces,

text: available

text: at

text: Matthias

text: Aschenbrenner

text: and

text: Christopher

text: J.

text: Hillar,

text: Finite

text: generation

text: of

text: symmetric

text: ideals,

text: Trans.

text: Amer.

text: Math.

text: Soc.

text: Erratum

text: for

text: “Finite

text: generation

text: of

text: symmetric

text: ideals”,

text: Trans.

text: Amer.

text: Math.

text: Soc.

text: Satoshi

text: Aoki

text: and

text: Akimichi

text: Takemura,

text: Markov

text: chain

text: Monte

text: Carlo

text: exact

text: tests

text: for

text: incomplete

text: two-way

text: contingency

text: table,

text: Journal

text: of

text: Statistical

text: Computation

text: and

text: Simulation

text: no.

text: Jan

text: Draisma,

text: Rob

text: H.

text: Eggermont,

text: Robert

text: Krone,

text: and

text: Anton

text: Leykin,

text: Noetherianity

text: for

text: inﬁnite-dimensional

text: toric

text: varieties,

text: preprint,

text: arXiv:

text: ##LTLine##