Definition 8.1 .

Let X S 𝑋 𝑆 X\,\longrightarrow\,S italic_X ⟶ italic_S be a S 𝑆 S italic_S –scheme. Let d x 𝑑 𝑥 dx italic_d italic_x denote the image of x 𝑥 x italic_x under the canonical de Rham differentiation map d : 𝒪 X Ω X / S 1 : 𝑑 subscript 𝒪 𝑋 subscript superscript Ω 1 𝑋 𝑆 d\,:\,\mathcal{O}_{X}\,\longrightarrow\,\Omega^{1}_{X/S} italic_d : caligraphic_O start_POSTSUBSCRIPT italic_X end_POSTSUBSCRIPT ⟶ roman_Ω start_POSTSUPERSCRIPT 1 end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_X / italic_S end_POSTSUBSCRIPT . Let \mathcal{F} caligraphic_F be a coherent sheaf of 𝒪 X subscript 𝒪 𝑋 \mathcal{O}_{X} caligraphic_O start_POSTSUBSCRIPT italic_X end_POSTSUBSCRIPT –modules over X 𝑋 X italic_X . By a D X subscript 𝐷 𝑋 D_{X} italic_D start_POSTSUBSCRIPT italic_X end_POSTSUBSCRIPT module structure on \mathcal{F} caligraphic_F we mean a 𝒪 S subscript 𝒪 𝑆 \mathcal{O}_{S} caligraphic_O start_POSTSUBSCRIPT italic_S end_POSTSUBSCRIPT –linear homomorphism of sheaf of abelian groups : 𝒪 X Ω X / S 1 : subscript tensor-product subscript 𝒪 𝑋 subscript superscript Ω 1 𝑋 𝑆 \nabla\,:\,\mathcal{F}\,\longrightarrow\,\mathcal{F}\otimes_{\mathcal{O}_{X}}% \Omega^{1}_{X/S} ∇ : caligraphic_F ⟶ caligraphic_F ⊗ start_POSTSUBSCRIPT caligraphic_O start_POSTSUBSCRIPT italic_X end_POSTSUBSCRIPT end_POSTSUBSCRIPT roman_Ω start_POSTSUPERSCRIPT 1 end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_X / italic_S end_POSTSUBSCRIPT satisfying Leibniz rule which says that

( x f ) = f d x + x ( f ) , 𝑥 𝑓 tensor-product 𝑓 𝑑 𝑥 𝑥 𝑓 \nabla(xf)\,=\,f\otimes dx+x\nabla(f)\,, ∇ ( italic_x italic_f ) = italic_f ⊗ italic_d italic_x + italic_x ∇ ( italic_f ) , (8.1)

Definition 2.3 .

Given a left pre-Lie algebra ( L , ) 𝐿 normal-⊳ (L,\vartriangleright) ( italic_L , ⊳ ) , the associated symmetric brace operations { # , , # | # } : L n L L normal-: conditional-set normal-# normal-… normal-# normal-# normal-→ tensor-product superscript 𝐿 direct-product absent 𝑛 𝐿 𝐿 \{\#,\ldots,\#|\#\}:L^{\odot n}\otimes L\to L { # , … , # | # } : italic_L start_POSTSUPERSCRIPT ⊙ italic_n end_POSTSUPERSCRIPT ⊗ italic_L → italic_L are defined recursively by (see [ 22 , 10 ] )

{ x } = x , 𝑥 𝑥 \{x\}=x, { italic_x } = italic_x ,
{ y | x } = y x , conditional-set 𝑦 𝑥 𝑦 𝑥 \{y|x\}=y\vartriangleright x, { italic_y | italic_x } = italic_y ⊳ italic_x ,
{ y 1 , , y k | x } = y 1 { y 2 , , y k | x } - j = 2 k { y 2 , , y 1 y j , y k | x } . conditional-set subscript 𝑦 1 subscript 𝑦 𝑘 𝑥 subscript 𝑦 1 conditional-set subscript 𝑦 2 subscript 𝑦 𝑘 𝑥 superscript subscript 𝑗 2 𝑘 conditional-set subscript 𝑦 2 subscript 𝑦 1 subscript 𝑦 𝑗 subscript 𝑦 𝑘 𝑥 \{y_{1},\ldots,y_{k}|x\}=y_{1}\vartriangleright\{y_{2},\ldots,y_{k}|x\}-\sum_{% j=2}^{k}\{y_{2},\ldots,y_{1}\vartriangleright y_{j},\ldots y_{k}|x\}. { italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , … , italic_y start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT | italic_x } = italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ⊳ { italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , … , italic_y start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT | italic_x } - ∑ start_POSTSUBSCRIPT italic_j = 2 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_k end_POSTSUPERSCRIPT { italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , … , italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ⊳ italic_y start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT , … italic_y start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT | italic_x } .

Definition 6 ( MEXIT coupling) .

Suppose that the MEXIT equation holds for all genealogical states 𝐬 𝐬 {\bf s} bold_s :

r ( 𝐬 , 𝐬 ) = p ( 𝐬 ) q ( 𝐬 ) . 𝑟 𝐬 𝐬 𝑝 𝐬 𝑞 𝐬 r({\bf s},{\bf s})\quad=\quad p({\bf s})\wedge q({\bf s})\,. italic_r ( bold_s , bold_s ) = italic_p ( bold_s ) ∧ italic_q ( bold_s ) . (4)

Then the coupling is a maximal exit coupling ( MEXIT coupling).


Definition 1 ( Agarwal et al. [ 2012 ] ) .

For a given constraint convex set 𝒞 𝒞 \mathcal{C} caligraphic_C , and a function class 𝒮 𝒮 \mathcal{S} caligraphic_S , a first-order stochastic oracle is a random mapping π : 𝒞 × 𝒮 × d normal-: 𝜋 normal-→ 𝒞 𝒮 superscript 𝑑 \pi:\mathcal{C}\times\mathcal{S}\to\mathbb{R}\times{\mathbb{R}^{d}} italic_π : caligraphic_C × caligraphic_S → blackboard_R × blackboard_R start_POSTSUPERSCRIPT italic_d end_POSTSUPERSCRIPT of the form

ϕ ( θ , f ) = ( f ~ ( θ ) , g ( θ ) ) , italic-ϕ 𝜃 𝑓 ~ 𝑓 𝜃 𝑔 𝜃 \phi(\theta,f)=(\tilde{f}(\theta),g(\theta)), italic_ϕ ( italic_θ , italic_f ) = ( ~ start_ARG italic_f end_ARG ( italic_θ ) , italic_g ( italic_θ ) ) ,

such that

𝔼 f ~ ( θ ) = f ( θ ) ; 𝔼 g ( θ ) = f ( θ ) , formulae-sequence 𝔼 ~ 𝑓 𝜃 𝑓 𝜃 𝔼 𝑔 𝜃 𝑓 𝜃 \mathbb{E}\tilde{f}(\theta)=f(\theta);\qquad\ \mathbb{E}g(\theta)=\nabla f(% \theta), blackboard_E ~ start_ARG italic_f end_ARG ( italic_θ ) = italic_f ( italic_θ ) ; blackboard_E italic_g ( italic_θ ) = ∇ italic_f ( italic_θ ) ,

and there exists a constant C < 𝐶 C<\infty italic_C < ∞ such that for every θ d 𝜃 superscript 𝑑 \theta\in{\mathbb{R}^{d}} italic_θ ∈ blackboard_R start_POSTSUPERSCRIPT italic_d end_POSTSUPERSCRIPT

𝔼 [ g ( θ ) - f ( θ ) 2 ] C ( 1 + θ 2 ) . 𝔼 delimited-[] superscript norm 𝑔 𝜃 𝑓 𝜃 2 𝐶 1 superscript norm 𝜃 2 \mathbb{E}[\|g(\theta)-\nabla f(\theta)\|^{2}]\leq C(1+\|\theta\|^{2}). blackboard_E [ ∥ italic_g ( italic_θ ) - ∇ italic_f ( italic_θ ) ∥ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ] ≤ italic_C ( 1 + ∥ italic_θ ∥ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ) .

Definition 2.1 .

We will say that a strictly increasing sequence of non-negative real numbers ( λ k ) k = 0 superscript subscript subscript 𝜆 𝑘 𝑘 0 (\lambda_{k})_{k=0}^{\infty} ( italic_λ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_k = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT has the Rapid Increase Property (RIP) if λ k + 1 2 λ k subscript 𝜆 𝑘 1 2 subscript 𝜆 𝑘 \lambda_{k+1}\geq 2\lambda_{k} italic_λ start_POSTSUBSCRIPT italic_k + 1 end_POSTSUBSCRIPT ≥ 2 italic_λ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT for every k 0 𝑘 0 k\geq 0 italic_k ≥ 0 .

We will call a function of the form \linenomath

p ( x ) = x α - x β , 𝑝 𝑥 superscript 𝑥 𝛼 superscript 𝑥 𝛽 \displaystyle p(x)=x^{\alpha}-x^{\beta}, italic_p ( italic_x ) = italic_x start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - italic_x start_POSTSUPERSCRIPT italic_β end_POSTSUPERSCRIPT ,
\endlinenomath

where 0 α < β , 0 𝛼 𝛽 0\leq\alpha<\beta, 0 ≤ italic_α < italic_β , a spike function .


Definition 4.6 (Taft algebra) .

Let q 𝑞 q italic_q be a primitive normal-ℓ \ell roman_ℓ -th root of unity prime) and let T q subscript 𝑇 𝑞 T_{q} italic_T start_POSTSUBSCRIPT italic_q end_POSTSUBSCRIPT be the Hopf algebra generated by g , x 𝑔 𝑥 g,x italic_g , italic_x with relations and coproduct as follows:

g = 1 x = 0 x g = q g x formulae-sequence superscript 𝑔 1 formulae-sequence superscript 𝑥 0 𝑥 𝑔 𝑞 𝑔 𝑥 g^{\ell}=1\qquad x^{\ell}=0\qquad xg=qgx italic_g start_POSTSUPERSCRIPT roman_ℓ end_POSTSUPERSCRIPT = 1 italic_x start_POSTSUPERSCRIPT roman_ℓ end_POSTSUPERSCRIPT = 0 italic_x italic_g = italic_q italic_g italic_x
Δ ( g ) = g g Δ ( x ) = g x + x 1 formulae-sequence Δ 𝑔 tensor-product 𝑔 𝑔 Δ 𝑥 tensor-product 𝑔 𝑥 tensor-product 𝑥 1 \Delta(g)=g\otimes g\qquad\Delta(x)=g\otimes x+x\otimes 1 roman_Δ ( italic_g ) = italic_g ⊗ italic_g roman_Δ ( italic_x ) = italic_g ⊗ italic_x + italic_x ⊗ 1

T q subscript 𝑇 𝑞 T_{q} italic_T start_POSTSUBSCRIPT italic_q end_POSTSUBSCRIPT has dimension 2 superscript normal-ℓ 2 \ell^{2} roman_ℓ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT and decomposes into a Radford biproduct product T q = K A = [ x ] [ ] subscript 𝑇 𝑞 right-normal-factor-semidirect-product 𝐾 𝐴 right-normal-factor-semidirect-product delimited-[] 𝑥 delimited-[] subscript normal-ℓ T_{q}=K\rtimes A=\mathbb{C}[x]\rtimes\mathbb{C}[\mathbb{Z}_{\ell}] italic_T start_POSTSUBSCRIPT italic_q end_POSTSUBSCRIPT = italic_K ⋊ italic_A = blackboard_C [ italic_x ] ⋊ blackboard_C [ blackboard_Z start_POSTSUBSCRIPT roman_ℓ end_POSTSUBSCRIPT ] where the A 𝐴 A italic_A -action and -coaction on K 𝐾 K italic_K is given by g . x = q x formulae-sequence 𝑔 𝑥 𝑞 𝑥 g.x=qx italic_g . italic_x = italic_q italic_x and δ ( x ) = g x 𝛿 𝑥 tensor-product 𝑔 𝑥 \delta(x)=g\otimes x italic_δ ( italic_x ) = italic_g ⊗ italic_x . It is a self-dual Hopf algebra via the linear forms g * : g , x q , 0 fragments superscript 𝑔 normal-: g normal-, x maps-to q normal-, 0 g^{*}:g,x\mapsto q,0 italic_g start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT : italic_g , italic_x ↦ italic_q , 0 and x * : g , x 1 , 1 fragments superscript 𝑥 normal-: g normal-, x maps-to 1 normal-, 1 x^{*}:g,x\mapsto 1,1 italic_x start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT : italic_g , italic_x ↦ 1 , 1 .

The Taft algebra appears naturally as the Borel part of the small quantum groups u q - 1 / 2 ( 𝔰 𝔩 2 ) + subscript 𝑢 superscript 𝑞 1 2 superscript 𝔰 subscript 𝔩 2 u_{q^{-1/2}}(\mathfrak{sl}_{2})^{+} italic_u start_POSTSUBSCRIPT italic_q start_POSTSUPERSCRIPT - 1 / 2 end_POSTSUPERSCRIPT end_POSTSUBSCRIPT ( fraktur_s fraktur_l start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ) start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT . The Drinfel’d double D T q normal-D subscript 𝑇 𝑞 \mathrm{D}T_{q} roman_D italic_T start_POSTSUBSCRIPT italic_q end_POSTSUBSCRIPT is generated by two isomorphic Taft algebras g , x 𝑔 𝑥 g,x italic_g , italic_x and g * , x * superscript 𝑔 superscript 𝑥 g^{*},x^{*} italic_g start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT , italic_x start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT with relations

x * g = q - 1 g x * x g * = q - 1 g * x x x * - q x * x = g - g * q - q - 1 formulae-sequence superscript 𝑥 𝑔 superscript 𝑞 1 𝑔 superscript 𝑥 formulae-sequence 𝑥 superscript 𝑔 superscript 𝑞 1 superscript 𝑔 𝑥 𝑥 superscript 𝑥 𝑞 superscript 𝑥 𝑥 𝑔 superscript 𝑔 𝑞 superscript 𝑞 1 x^{*}g=q^{-1}gx^{*}\qquad xg^{*}=q^{-1}g^{*}x\qquad xx^{*}-qx^{*}x=\frac{g-g^{% *}}{q-q^{-1}} italic_x start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT italic_g = italic_q start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_g italic_x start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT italic_x italic_g start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT = italic_q start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_g start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT italic_x italic_x italic_x start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT - italic_q italic_x start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT italic_x = divide start_ARG italic_g - italic_g start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT end_ARG start_ARG italic_q - italic_q start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT end_ARG

It has the full quantum group as quotient by the central element g g * - 1 𝑔 superscript 𝑔 1 gg^{*}-1 italic_g italic_g start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT - 1 .


Definition 2.8 .

A point ( α , β ) Ω 𝛼 𝛽 normal-Ω (\alpha,\beta)\in\Omega ( italic_α , italic_β ) ∈ roman_Ω , ξ 1 α ξ 2 subscript 𝜉 1 𝛼 subscript 𝜉 2 \xi_{1}\leq\alpha\leq\xi_{2} italic_ξ start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ≤ italic_α ≤ italic_ξ start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT is said to lie in the domain of influence of the stable root y = ϕ ( x ) 𝑦 italic-ϕ 𝑥 y=\phi(x) italic_y = italic_ϕ ( italic_x ) if the solution of the problem

d y / d τ = g ( α , y ) , y ( 0 ) = β formulae-sequence 𝑑 𝑦 𝑑 𝜏 𝑔 𝛼 𝑦 𝑦 0 𝛽 dy/d\tau=g(\alpha,y),\ \ y(0)=\beta italic_d italic_y / italic_d italic_τ = italic_g ( italic_α , italic_y ) , italic_y ( 0 ) = italic_β

exists and remains in Ω normal-Ω \Omega roman_Ω for all τ > 0 𝜏 0 \tau>0 italic_τ > 0 , and if it tends to ϕ ( α ) italic-ϕ 𝛼 \phi(\alpha) italic_ϕ ( italic_α ) , as τ + normal-→ 𝜏 \tau\rightarrow+\infty italic_τ → + ∞ .


Definition 4 .

Operator p : X × X × X X normal-: 𝑝 normal-→ 𝑋 𝑋 𝑋 𝑋 p:X\times X\times X\rightarrow X italic_p : italic_X × italic_X × italic_X → italic_X is called Maltsev if

x , y X p ( x , x , y ) = p ( y , x , x ) = y . for-all 𝑥 𝑦 𝑋 𝑝 𝑥 𝑥 𝑦 𝑝 𝑦 𝑥 𝑥 𝑦 \forall x,y\in X\Rightarrow p(x,x,y)=p(y,x,x)=y. ∀ italic_x , italic_y ∈ italic_X ⇒ italic_p ( italic_x , italic_x , italic_y ) = italic_p ( italic_y , italic_x , italic_x ) = italic_y .
Definition 5 .

Operator p : X × X × X X normal-: 𝑝 normal-→ 𝑋 𝑋 𝑋 𝑋 p:X\times X\times X\rightarrow X italic_p : italic_X × italic_X × italic_X → italic_X is called a majority operator if

x , y X p ( x , x , y ) = p ( x , y , x ) = p ( y , x , x ) = x . for-all 𝑥 𝑦 𝑋 𝑝 𝑥 𝑥 𝑦 𝑝 𝑥 𝑦 𝑥 𝑝 𝑦 𝑥 𝑥 𝑥 \forall x,y\in X\Rightarrow p(x,x,y)=p(x,y,x)=p(y,x,x)=x. ∀ italic_x , italic_y ∈ italic_X ⇒ italic_p ( italic_x , italic_x , italic_y ) = italic_p ( italic_x , italic_y , italic_x ) = italic_p ( italic_y , italic_x , italic_x ) = italic_x .

Definition 2.1.4 .

For ω A r , s ( M ) 𝜔 superscript 𝐴 𝑟 𝑠 𝑀 \omega\in A^{r,s}(M) italic_ω ∈ italic_A start_POSTSUPERSCRIPT italic_r , italic_s end_POSTSUPERSCRIPT ( italic_M ) we define an exterior product operator e ( ω ) : A p , q ( M ) A p + q , r + s ( M ) : 𝑒 𝜔 superscript 𝐴 𝑝 𝑞 𝑀 superscript 𝐴 𝑝 𝑞 𝑟 𝑠 𝑀 e(\omega):A^{p,q}(M)\to A^{p+q,r+s}(M) italic_e ( italic_ω ) : italic_A start_POSTSUPERSCRIPT italic_p , italic_q end_POSTSUPERSCRIPT ( italic_M ) → italic_A start_POSTSUPERSCRIPT italic_p + italic_q , italic_r + italic_s end_POSTSUPERSCRIPT ( italic_M ) by

e ( ω ) η = ω η . 𝑒 𝜔 𝜂 𝜔 𝜂 e(\omega)\eta=\omega\wedge\eta. italic_e ( italic_ω ) italic_η = italic_ω ∧ italic_η .

Definition 1.9 .

We say f : M : 𝑓 𝑀 f:M\to\mathbb{R} italic_f : italic_M → blackboard_R is a - 1 1 -1 - 1 -affine function, if for any unit speed geodesic γ ( t ) 𝛾 𝑡 \gamma(t) italic_γ ( italic_t ) ,

[ f γ ( t ) ] ′′ - f γ ( t ) = 0 . superscript delimited-[] 𝑓 𝛾 𝑡 ′′ 𝑓 𝛾 𝑡 0 [f\circ\gamma(t)]^{\prime\prime}-f\circ\gamma(t)=0. [ italic_f ∘ italic_γ ( italic_t ) ] start_POSTSUPERSCRIPT ′ ′ end_POSTSUPERSCRIPT - italic_f ∘ italic_γ ( italic_t ) = 0 . (1.9)
Definition 2.2 .

We say that a function u 𝑢 u italic_u is differentiable at x Reg(M) 𝑥 Reg(M) x\in\text{Reg(M)} italic_x ∈ Reg(M) , if there exists a vector in T x subscript 𝑇 𝑥 T_{x} italic_T start_POSTSUBSCRIPT italic_x end_POSTSUBSCRIPT , denoted by u ( x ) 𝑢 𝑥 \nabla u(x) ∇ italic_u ( italic_x ) , such that for any geodesic γ ( t ) 𝛾 𝑡 \gamma(t) italic_γ ( italic_t ) with γ ( 0 ) = x 𝛾 0 𝑥 \gamma(0)=x italic_γ ( 0 ) = italic_x ,

u ( γ ( t ) ) = u ( x ) + u ( x ) , γ + ( 0 ) t + o ( t ) . 𝑢 𝛾 𝑡 𝑢 𝑥 𝑢 𝑥 superscript 𝛾 0 𝑡 𝑜 𝑡 u(\gamma(t))=u(x)+\langle\nabla u(x),\gamma^{+}(0)\rangle t+o(t). italic_u ( italic_γ ( italic_t ) ) = italic_u ( italic_x ) + ⟨ ∇ italic_u ( italic_x ) , italic_γ start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT ( 0 ) ⟩ italic_t + italic_o ( italic_t ) .

Definition 1.12 .

A function f : n * normal-: 𝑓 normal-⟶ superscript 𝑛 superscript f:\mathbb{Z}^{n}\longrightarrow\mathbb{R}^{*} italic_f : blackboard_Z start_POSTSUPERSCRIPT italic_n end_POSTSUPERSCRIPT ⟶ blackboard_R start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT is called a quadratic form if

f ( 𝐚 + 𝐛 + 𝐜 ) f ( 𝐚 + 𝐛 ) - 1 f ( 𝐛 + 𝐜 ) - 1 f ( 𝐜 + 𝐚 ) - 1 f ( 𝐚 ) f ( 𝐛 ) f ( 𝐜 ) = 1 , 𝑓 𝐚 𝐛 𝐜 𝑓 superscript 𝐚 𝐛 1 𝑓 superscript 𝐛 𝐜 1 𝑓 superscript 𝐜 𝐚 1 𝑓 𝐚 𝑓 𝐛 𝑓 𝐜 1 f(\mathbf{a+b+c})f(\mathbf{a+b})^{-1}f(\mathbf{b+c})^{-1}f(\mathbf{c+a})^{-1}f% (\mathbf{a})f(\mathbf{b})f(\mathbf{c})=1, italic_f ( bold_a + bold_b + bold_c ) italic_f ( bold_a + bold_b ) start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_f ( bold_b + bold_c ) start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_f ( bold_c + bold_a ) start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_f ( bold_a ) italic_f ( bold_b ) italic_f ( bold_c ) = 1 , (1.10)

for 𝐚 , 𝐛 , 𝐜 n 𝐚 𝐛 𝐜 superscript 𝑛 \mathbf{a,b,c}\in\mathbb{Z}^{n} bold_a , bold_b , bold_c ∈ blackboard_Z start_POSTSUPERSCRIPT italic_n end_POSTSUPERSCRIPT .


Definition 2 .

Let T e subscript 𝑇 𝑒 T_{e} italic_T start_POSTSUBSCRIPT italic_e end_POSTSUBSCRIPT denote the number of pairs ( a , b ) 𝑎 𝑏 (a,b) ( italic_a , italic_b ) such that

e = a - b d 𝑒 𝑎 𝑏 𝑑 \displaystyle e=a-bd italic_e = italic_a - italic_b italic_d

where a , b 𝑎 𝑏 a,b italic_a , italic_b are integers on the intervals 0 a < 2 + m 0 𝑎 superscript 2 normal-ℓ 𝑚 0\leq a<2^{\ell+m} 0 ≤ italic_a < 2 start_POSTSUPERSCRIPT roman_ℓ + italic_m end_POSTSUPERSCRIPT and 0 b < 2 0 𝑏 superscript 2 normal-ℓ 0\leq b<2^{\ell} 0 ≤ italic_b < 2 start_POSTSUPERSCRIPT roman_ℓ end_POSTSUPERSCRIPT .


Definition 3.3 .

The result of mounting the directory d superscript 𝑑 d^{\prime} italic_d start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT at the location p 𝑝 p italic_p into the directory d 𝑑 d italic_d is given by

d ^ ( f ) = { d ( f ) f = ( p ) ( f ) d ( f ) otherwise ^ 𝑑 𝑓 cases superscript 𝑑 superscript 𝑓 𝑓 𝑝 superscript 𝑓 𝑑 𝑓 otherwise \hat{d}\left(f\right)=\begin{cases}d^{\prime}\left(f^{\prime}\right)&f=(p)(f^{% \prime})\\ d(f)&\mathrm{otherwise}\\ \end{cases} ^ start_ARG italic_d end_ARG ( italic_f ) = { start_ROW start_CELL italic_d start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT ( italic_f start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT ) end_CELL start_CELL italic_f = ( italic_p ) ( italic_f start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT ) end_CELL end_ROW start_ROW start_CELL italic_d ( italic_f ) end_CELL start_CELL roman_otherwise end_CELL end_ROW

Definition 1 .

The symmetric measure μ 𝜇 \mu italic_μ on the space of perimeter 2 triangles is given by the pushforward of the uniform probability measure on the unit sphere under the map

a = 1 - x 2 , b = 1 - y 2 , c = 1 - z 2 . formulae-sequence 𝑎 1 superscript 𝑥 2 formulae-sequence 𝑏 1 superscript 𝑦 2 𝑐 1 superscript 𝑧 2 a=1-x^{2},\quad b=1-y^{2},\quad c=1-z^{2}. italic_a = 1 - italic_x start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT , italic_b = 1 - italic_y start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT , italic_c = 1 - italic_z start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT .

Definition 8.2 .

The Minkowski sum of two GFs a ( 𝐭 ) 𝑎 𝐭 a(\mathbf{t}) italic_a ( bold_t ) and b ( 𝐭 ) 𝑏 𝐭 b(\mathbf{t}) italic_b ( bold_t ) is the unique GF c ( 𝐭 ) 𝑐 𝐭 c(\mathbf{t}) italic_c ( bold_t ) with

supp ( c ) = supp ( a ) supp ( b ) , supp 𝑐 direct-sum supp 𝑎 supp 𝑏 \textup{supp}(c)=\textup{supp}(a)\oplus\textup{supp}(b), supp ( italic_c ) = supp ( italic_a ) ⊕ supp ( italic_b ) ,

where direct-sum \oplus is the Minkowski sum of two point sets.


Definition VII.1 .

Attacker action. The attacker’s action consists of hiding her malicious activity for a specified period of time. Such an action would restore all of the kernel address space location to their original state, thus avoid detection in case the verifier initiates a PowerAlert -porotocol attestation process. Formally, let c : + : 𝑐 superscript c:\mathcal{R}^{+}\longrightarrow\mathcal{B} italic_c : caligraphic_R start_POSTSUPERSCRIPT + end_POSTSUPERSCRIPT ⟶ caligraphic_B be the function defining the state of the attacker’s malicious activity at any time t > 0 𝑡 0 t>0 italic_t > 0 , i.e.,

c ( t ) = { iff attacker is active at time t otherwise fragments c fragments ( t ) fragments { top iff attacker is active at time t bottom otherwise c(t)=\left\{\begin{aligned} \displaystyle\top&\displaystyle\quad\mbox{iff % attacker is active at time t}\\ \displaystyle\bot&\displaystyle\quad\mbox{otherwise}\end{aligned}\right. italic_c ( italic_t ) = { start_ROW start_CELL ⊤ end_CELL start_CELL iff attacker is active at time t end_CELL end_ROW start_ROW start_CELL ⊥ end_CELL start_CELL otherwise end_CELL end_ROW

Let 𝒞 𝒞 \mathcal{C} caligraphic_C be the state of all such state functions. We slightly abuse the notation to write c ( [ t a , t b ] ) 𝑐 subscript 𝑡 𝑎 subscript 𝑡 𝑏 c([t_{a},t_{b}]) italic_c ( [ italic_t start_POSTSUBSCRIPT italic_a end_POSTSUBSCRIPT , italic_t start_POSTSUBSCRIPT italic_b end_POSTSUBSCRIPT ] ) to refer to the state of the attacker’s activity in the time interval t a t t b subscript 𝑡 𝑎 𝑡 subscript 𝑡 𝑏 t_{a}\leq t\leq t_{b} italic_t start_POSTSUBSCRIPT italic_a end_POSTSUBSCRIPT ≤ italic_t ≤ italic_t start_POSTSUBSCRIPT italic_b end_POSTSUBSCRIPT .

An attacker’s action is therefore defined as a function a 1 : 𝒞 𝒞 : subscript 𝑎 1 𝒞 𝒞 a_{1}:\mathcal{C}\longrightarrow\mathcal{C} italic_a start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT : caligraphic_C ⟶ caligraphic_C that changes the state of the attacker’s activity for a period of time α 1 subscript 𝛼 1 \alpha_{1} italic_α start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT . Formally,

a 1 ( c ( [ t , t + α 1 ] ) = { iff c ( [ t , t + α 1 ] ) = c ( [ t , t + α 1 ] ) otherwise fragments subscript 𝑎 1 fragments ( c fragments ( fragments [ t , t subscript 𝛼 1 ] ) fragments { bottom iff 𝑐 𝑡 𝑡 subscript 𝛼 1 top 𝑐 𝑡 𝑡 subscript 𝛼 1 otherwise a_{1}(c([t,t+\alpha_{1}])=\left\{\begin{aligned} \displaystyle\bot&% \displaystyle\quad\mbox{iff }c([t,t+\alpha_{1}])=\top\\ \displaystyle c([t,t+\alpha_{1}])&\displaystyle\quad\mbox{otherwise}\end{% aligned}\right. italic_a start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ( italic_c ( [ italic_t , italic_t + italic_α start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ] ) = { start_ROW start_CELL ⊥ end_CELL start_CELL iff italic_c ( [ italic_t , italic_t + italic_α start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ] ) = ⊤ end_CELL end_ROW start_ROW start_CELL italic_c ( [ italic_t , italic_t + italic_α start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ] ) end_CELL start_CELL otherwise end_CELL end_ROW

Definition 5.2 (Group configuration) .

Let M 𝑀 M italic_M be a model of a strongly minimal theory, and let dim dimension \dim roman_dim the be associated dimension function on tuples.

\xy < 1.5 c m , 0 c m > : ( 1 , 0.2 ) * x ; ( 2 , 0.2 ) * y ; ( 0.8 , - 0.8 ) * z ; ( - 0.2 , 0 ) * a ; ( - 0.2 , - 1 ) * b ; ( - 0.2 , - 2 ) * c ; ( 1 , 0 ) * ; ( 0 , - 2 ) * * * \dir - ; ( 0 , - 2 ) * ; ( 0 , 0 ) * * * \dir - ; ( 0 , 0 ) * ; ( 2 , 0 ) * * * \dir - ; ( 2 , 0 ) * ; ( 0 , - 1 ) * * * \dir - ; \endxy fragments \xy 1.5 c m , 0 c m : fragments ( 1 , 0.2 ) x ; fragments ( 2 , 0.2 ) y ; fragments ( 0.8 , 0.8 ) z ; fragments ( 0.2 , 0 ) a ; fragments ( 0.2 , 1 ) b ; fragments ( 0.2 , 2 ) c ; fragments ( 1 , 0 ) ; fragments ( 0 , 2 ) \dir ; fragments ( 0 , 2 ) ; fragments ( 0 , 0 ) \dir ; fragments ( 0 , 0 ) ; fragments ( 2 , 0 ) \dir ; fragments ( 2 , 0 ) ; fragments ( 0 , 1 ) \dir ; \endxy \xy<1.5cm,0cm>:(1,0.2)*{x};(2,0.2)*{y};(0.8,-0.8)*{z};(-0.2,0)*{a};(-0.2,-1)*{% b};(-0.2,-2)*{c};(1,0)*{};(0,-2)*{}**\dir{-};(0,-2)*{};(0,0)*{}**\dir{-};(0,0)% *{};(2,0)*{}**\dir{-};(2,0)*{};(0,-1)*{}**\dir{-};\endxy < 1.5 italic_c italic_m , 0 italic_c italic_m > : ( 1 , 0.2 ) * italic_x ; ( 2 , 0.2 ) * italic_y ; ( 0.8 , - 0.8 ) * italic_z ; ( - 0.2 , 0 ) * italic_a ; ( - 0.2 , - 1 ) * italic_b ; ( - 0.2 , - 2 ) * italic_c ; ( 1 , 0 ) * ; ( 0 , - 2 ) * * * - ; ( 0 , - 2 ) * ; ( 0 , 0 ) * * * - ; ( 0 , 0 ) * ; ( 2 , 0 ) * * * - ; ( 2 , 0 ) * ; ( 0 , - 1 ) * * * - ;

The set { a , b , c , x , y , z } 𝑎 𝑏 𝑐 𝑥 𝑦 𝑧 \{\ a,b,c,x,y,z\ \} { italic_a , italic_b , italic_c , italic_x , italic_y , italic_z } of tuples is called a group configuration if there exists an integer n 𝑛 n italic_n such that


Definition 34 .

For x , y 2 ω 𝑥 𝑦 superscript 2 𝜔 x,y\in 2^{\omega} italic_x , italic_y ∈ 2 start_POSTSUPERSCRIPT italic_ω end_POSTSUPERSCRIPT , the join of x 𝑥 x italic_x and y 𝑦 y italic_y is x y direct-sum 𝑥 𝑦 x\oplus y italic_x ⊕ italic_y , defined by

( x y ) ( n ) = { x ( k ) if n = 2 k ; y ( k ) if n = 2 k + 1 . direct-sum 𝑥 𝑦 𝑛 cases 𝑥 𝑘 if 𝑛 2 𝑘 𝑦 𝑘 if 𝑛 2 𝑘 1 (x\oplus y)(n)=\begin{cases}x(k)&\text{ if }n=2k;\cr y(k)&\text{ if }n=2k+1.% \cr\end{cases} ( italic_x ⊕ italic_y ) ( italic_n ) = { start_ROW start_CELL italic_x ( italic_k ) end_CELL start_CELL if italic_n = 2 italic_k ; end_CELL end_ROW start_ROW start_CELL italic_y ( italic_k ) end_CELL start_CELL if italic_n = 2 italic_k + 1 . end_CELL end_ROW

We make a similar definition for σ 2 m 𝜎 superscript 2 𝑚 \sigma\in 2^{m} italic_σ ∈ 2 start_POSTSUPERSCRIPT italic_m end_POSTSUPERSCRIPT and τ 2 m 𝜏 superscript 2 𝑚 \tau\in 2^{m} italic_τ ∈ 2 start_POSTSUPERSCRIPT italic_m end_POSTSUPERSCRIPT or τ 2 m - 1 𝜏 superscript 2 𝑚 1 \tau\in 2^{m-1} italic_τ ∈ 2 start_POSTSUPERSCRIPT italic_m - 1 end_POSTSUPERSCRIPT : σ τ direct-sum 𝜎 𝜏 \sigma\oplus\tau italic_σ ⊕ italic_τ has domain 2 m 2 𝑚 2m 2 italic_m in the first case, and 2 m - 1 2 𝑚 1 2m-1 2 italic_m - 1 in the second, and

( σ τ ) ( n ) = { σ ( k ) if n = 2 k ; τ ( k ) if n = 2 k + 1 . direct-sum 𝜎 𝜏 𝑛 cases 𝜎 𝑘 if 𝑛 2 𝑘 𝜏 𝑘 if 𝑛 2 𝑘 1 (\sigma\oplus\tau)(n)=\begin{cases}\sigma(k)&\text{ if }n=2k;\cr\tau(k)&\text{% if }n=2k+1.\cr\end{cases} ( italic_σ ⊕ italic_τ ) ( italic_n ) = { start_ROW start_CELL italic_σ ( italic_k ) end_CELL start_CELL if italic_n = 2 italic_k ; end_CELL end_ROW start_ROW start_CELL italic_τ ( italic_k ) end_CELL start_CELL if italic_n = 2 italic_k + 1 . end_CELL end_ROW

If z 2 ω 𝑧 superscript 2 absent 𝜔 z\in 2^{\leq\omega} italic_z ∈ 2 start_POSTSUPERSCRIPT ≤ italic_ω end_POSTSUPERSCRIPT , we can view z 𝑧 z italic_z as a join, and define its left and right parts: If z = x y 𝑧 direct-sum 𝑥 𝑦 z=x\oplus y italic_z = italic_x ⊕ italic_y , then ( z ) = x 𝑧 𝑥 \ell(z)=x roman_ℓ ( italic_z ) = italic_x and r ( z ) = y 𝑟 𝑧 𝑦 r(z)=y italic_r ( italic_z ) = italic_y .