Analytic proof systems for λ-calculus: the elimination of transitivity, and why it matters

We introduce new proof systems G[β] and G _ext[β], which are equivalent to the standard equational calculi of λβ- and λβη- conversion, and which may be qualified as ‘analytic’ because it is possible to establish, by purely proof-theoretical methods, that in both of them the transitivity rule admits effective elimination. This key feature, besides its intrinsic conceptual significance, turns out to provide a common logical background to new and comparatively simple demonstrations—rooted in nice proof-theoretical properties of transitivity-free derivations—of a number of well-known and central results concerning β- and βη-reduction. The latter include the Church–Rosser theorem for both reductions, the Standardization theorem for β- reduction, as well as the Normalization (Leftmost reduction) theorem and the Postponement of η-reduction theorem for βη-reduction      

An Answer to S. Simons’ Question on the Maximal Monotonicity of the Sum of a Maximal Monotone Linear Operator and a Normal Cone Operator

The question whether or not the sum of two maximal monotone operators is maximal monotone under Rockafellar’s constraint qualification—that is, whether or not “the sum theorem” is true—is the most famous open problem in Monotone Operator Theory. In his 2008 monograph “From Hahn-Banach to Monotonicity”, Stephen Simons asked whether or not the sum theorem holds for the special case of a maximal monotone linear operator and a normal cone operator of a closed convex set provided that the interior of the set makes a nonempty intersection with the domain of the linear operator. In this note, we provide an affirmative answer to Simons’ question. In fact, we show that the sum theorem is true for a maximal monotone linear relation and a normal cone operator. The proof relies on Rockafellar’s formula for the Fenchel conjugate of the sum as well as some results featuring the Fitzpatrick function.      

Reducing prime graphs and recognizing circle graphs

We prove a reduction theorem for prime (simple) graphs in Cunningham’s sense. Roughly speaking this theorem says that every prime (simple) graph of ordern>5 “contains” a smaller prime graph of ordern−1. As an application we give a polynomial algorithm for recognizing circle graphs.     

Analysis of space–time discontinuous Galerkin method for nonlinear convection–diffusion problems

The paper presents the theory of the discontinuous Galerkin finite element method for the space–time discretization of a nonstationary convection–diffusion initial-boundary value problem with nonlinear convection and linear diffusion. The problem is not singularly perturbed with dominating convection. The discontinuous Galerkin method is applied separately in space and time using, in general, different space grids on different time levels and different polynomial degrees p and q in space and time dicretization. In the space discretization the nonsymmetric, symmetric and incomplete interior and boundary penalty (NIPG, SIPG, IIPG) approximation of diffusion terms is used. The paper is concerned with the proof of error estimates in “L ²(L ²)”- and “DG”-norm formed by the “L ²(H ¹)”-seminorm and penalty terms. A special technique based on the use of the Gauss–Radau interpolation and numerical integration has been used for the derivation of an abstract error estimate. In the “DG”-norm the error estimates are optimal with respect to the size of the space grid. They are optimal with respect to the time step, if the Dirichlet boundary condition has behaviour in time as a polynomial of degree ≤ q.     

Beth’s theorem in cardinality logics

We prove that the Beth definability theorem fails for a comprehensive class of first-order logics with cardinality quantifiers. In particular, we give a counterexample to Beth’s theorem forL(Q), which is finitary first-order logic (with identity) augmented with the quantifier “there exists uncountably many”. This research was partially supported by NSF GP29254.     

Lambda-structure on Grothendieck groups of Hermitian vector bundles

We define a “compactification” of the representation ring of the linear group scheme over Specℤ, in the spirit of Arakelov geometry. We show that it is a λ-ring which is canonically isomorphic to a localized polynomial ring and that it plays a universal role with respect to natural operations on theK ₀-theory of hermitian bundles defined by Gillet-Soulé. As a byproduct, we prove that the natural pre-λ-ring structure of theK ₀-theory of hermitian bundles is a λ-ring structure. This last result plays a key role in the proof of the main results of [18] and [12].     

On the multiplier conjecture

The Multiplier Theorem is a celebrated theorem in the Design theory. The conditionp>λ is crucial to all known proofs of the multiplier theorem. However in all known examples of difference sets μ _p . is a multiplier for every primep with (p, v)=1 andp‖n. Thus there is the multiplier conjecture: “The multiplier theorem holds without the assumption thatp>λ”. The general form of the multiplier theorem may be viewed as an attempt to partially resolve the multiplier conjecture, where the assumption “p>λ” is replaced by “n ₁>λ”. Since then Newman (1963), Turyn (1964), and McFarland (1970) attempted to partially resolve the multiplier conjecture (see [7], [8], [9]). This paper will prove the following result using the representation theory of finite groups and the algebraic number theory: LetG be an abelian group of orderv,v ₀ be the exponent ofG, andD be a (v, k, λ)-difference set inG. Ifn=2_{n 1}, then the general form of the multiplier theorem holds without the assumption thatn ₁>λ in any of the following cases:

Zéros d’applications holomorphes deC n dansC n

It is known that, unlike the one dimensional case it is not possible to find an upper bound for the zeros of an entire map fromC ⁿ toC ⁿ ,n≥2, in terms of the growth of the map. However, if we only consider the “non-degenerate” zeros, that is, the zeros where the jacobian is not “too small”, it becomes possible. We give a new proof of this fact.      

Large continuum,oracles

Our main theorem is about iterated forcing for making the continuum larger than ℵ₂. We present a generalization of [2] which deal with oracles for random, (also for other cases and generalities), by replacing ℵ₁,ℵ₂ by λ, λ ⁺ (starting with λ = λ ^<λ > ℵ₁). Well, we demand absolute c.c.c. So we get, e.g. the continuum is λ ⁺ but we can get cov(meagre) = λ and we give some applications. As in non-Cohen oracles [2], it is a “partial” countable support iteration but it is c.c.c.     

Polynomial Hierarchy, Betti Numbers, and a Real Analogue of Toda’s Theorem

Toda (in SIAM J. Comput. 20(5):865–877, 1991) proved in 1989 that the (discrete) polynomial time hierarchy, PH, is contained in the class P ^#P , namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity class #P. This result, which illustrates the power of counting, is considered to be a seminal result in computational complexity theory. An analogous result in the complexity theory over the reals (in the sense of Blum–Shub–Smale real machines in Bull. Am. Math. Soc. (NS) 21(1): 1–46, 1989) has been missing so far. In this paper we formulate and prove a real analogue of Toda’s theorem. Unlike Toda’s proof in the discrete case, which relied on sophisticated combinatorial arguments, our proof is topological in nature. As a consequence of our techniques, we are also able to relate the computational hardness of two extremely well-studied problems in algorithmic semi-algebraic geometry: the problem of deciding sentences in the first-order theory of the reals with a constant number of quantifier alternations, and that of computing Betti numbers of semi-algebraic sets. We obtain a polynomial time reduction of the compact version of the first problem to the second. This latter result may be of independent interest to researchers in algorithmic semi-algebraic geometry.     

Illuminating Spindle Convex Bodies and Minimizing the Volume of Spherical Sets of Constant Width

A subset of the d-dimensional Euclidean space having nonempty interior is called a spindle convex body if it is the intersection of (finitely or infinitely many) congruent d-dimensional closed balls. The spindle convex body is called a “fat” one, if it contains the centers of its generating balls. The core part of this paper is an extension of Schramm’s theorem and its proof on illuminating convex bodies of constant width to the family of “fat” spindle convex bodies. Also, this leads to the spherical analog of the well-known Blaschke–Lebesgue problem.     

Sequent calculi for branching time temporal logics of knowledge and beliefwith awareness: Completeness and decidability

In this paper, we consider branching time temporal logic CT L with epistemic modalities for knowledge (belief) and with awareness operators. These logics involve the discrete-time linear temporal logic operators “next” and “until” with the branching temporal logic operator “on all paths”. In addition, the temporal logic of knowledge (belief) contains an indexed set of unary modal operators “agent i knows” (“agent i believes”). In a language of these logics, there are awareness operators. For these logics, we present sequent calculi with a restricted cut rule. Thus, we get proof systems where proof-search becomes decidable. The soundness and completeness for these calculi are proved. Published in Lietuvos Matematikos Rinkinys, Vol. 47, No. 3, pp. 328–340, July–September, 2007.     

Logics with disjunction and proof by cases

This paper is a contribution to the general study of consequence relations which contain (definable) connective of “disjunction”. Our work is centered around the “proof by cases property”, we present several of its equivalent definitions, and show some interesting applications, namely in constructing axiomatic systems for intersections of logics and recognizing weakly implicative fuzzy logics among the weakly implicative ones. The work of the first author was supported by the National Foundation of Natural Sciences of China (Grant no. 60663002) and by the Grant Project of science and technology of The Education Department of Jiangxi Province under Grant no. 200618. The work of the second author was supported by grant A100300503 of the Grant Agency of the Academy of Sciences of the Czech Republic and by Institutional Research Plan AVOZ10300504.     

An identity of Andrews, multiple integrals, and very-well-poised hypergeometric series

We give a new proof of a theorem of Zudilin that equates a very-well-poised hypergeometric series and a particular multiple integral. This integral generalizes integrals of Vasilenko and Vasilyev which were proposed as tools in the study of the arithmetic behaviour of values of the Riemann zeta function at integers. Our proof is based on limiting cases of a basic hypergeometric identity of Andrews. Dedicated to Richard Askey on the occasion of his 70th birthday. Research partially supported by the programme “Improving the Human Research Potential” of the European Commission, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe”. 2000 Mathematics Subject Classification Primary—33C20; Secondary—11J72     

Transplantation harmonique,transplantation par modules,et théorèmes isopérimétriques

Summary The “harmonic transplantation” allows to extend some isoperimetric theorems, so far proved by conformal mapping, to higher connectivity and to higher dimensions; for the first eigenvalue λ₁ of a membrane, it again can give only upper bounds.—The “transplantation by moduli” is much more flexible; for example, it leads to a simple one-dimensional interpretation of the Rayleigh-Faber-Krahn theorem.      

Efficient Estimation of Spectral Functionals for Continuous-Time Stationary Models

The paper considers a problem of construction of asymptotically efficient estimators for functionals defined on a class of spectral densities, and bounding the minimax mean square risks. We define the concepts of H- and IK-efficiency of estimators, based on the variants of Hájek-Ibragimov-Khas’minskii convolution theorem and Hájek-Le Cam local asymptotic minimax theorem, respectively, and show that the simple “plug-in” statistic Φ(I _T ), where I _T =I _T (λ) is the periodogram of the underlying stationary Gaussian process X(t) with an unknown spectral density θ(λ), λ∈ℝ, is H- and IK-asymptotically efficient estimator for a linear functional Φ(θ), while for a nonlinear smooth functional Φ(θ) an H- and IK-asymptotically efficient estimator is the statistic F([^(q)]_T)\Phi(\widehat{\theta}_{T}), where [^(q)]_T\widehat{\theta}_{T} is a suitable sequence of the so-called “undersmoothed” kernel estimators of the unknown spectral density θ(λ). Exact asymptotic bounds for minimax mean square risks of estimators of linear functionals are also obtained.     

On the Lüroth semigroup of curves lying on a smooth quadric

For a smooth irreducible complete algebraic curveC the “gaps” are the integersn such that every linear series of degreen has at least a base point. The Lüroth semigroup S_C of a curveC is the subsemigroup ofN whose elements are not gaps. In this paper we deal with irreducible smooth curves of type (a, b) on a smooth quadricQ. The main result is an algorithm by which we can say if some integer λ∈N is a gap or is in S_C. In the general case there are integers λ which are undecidable. For curves such as complete intersection, arithmetically Cohen-Macaulay or Buchsbaum, we are able to describe explicitly “intervals” of gaps and “intervals” of integers which belong to S_C. For particular cases we can completely determine S_C, by giving just the type of the curve (in particular the degree and the genus). Work done with financial support of M.U.R.S.T. while the authors were members of G.N.S.A.G.A. of C.N.R.     

Lifting elementary embeddings <Emphasis Type="Italic">j</Emphasis>: <Emphasis Type="Italic">V</Emphasis><Subscript>λ</Subscript> → <Emphasis Type="Italic">V</Emphasis><Subscript>λ</Subscript>

We describe a fairly general procedure for preserving I₃ embeddings j: V _λ → V _λ via λ-stage reverse Easton iterated forcings. We use this method to prove that, assuming the consistency of an I₃ embedding, V = HOD is consistent with the theory ZFC + WA where WA is an axiom schema in the language {∈, j} asserting a strong but not inconsistent form of “there is an elementary embedding V → V”. This improves upon an earlier result in which consistency was established assuming an I₁ embedding.      

r-entropy,equipartition, and Ornstein’s isomorphism theorem inR n

A new approach is given to the entropy of a probability-preserving group action (in the context ofZ and ofR _n ), by defining an approximate “r-entropy”, 0<r<1, and lettingr → 0. If the usual entropy may be described as the growth rate of the number of essential names, then ther-entropy is the growth rate of the number of essential “groups of names” of width≦r, in an appropriate sense. The approach is especially useful for actions of continuous groups. We apply these techniques to state and prove a “second order” equipartition theorem forZ _m ×R _n and to give a “natural” proof of Ornstein’s isomorphism theorem for Bernoulli actions ofZ _m ×R _n , as well as a characterization of such actions which seems to be the appropriate generalization of “finitely determined”.     

Commutators and compressions

We present a short proof of the known theorem that every operator, not of the formλI + compact, whereλ ≢ 0, is a commutator. The second author gratefully acknowledges the support of the National Science Foundation.