Search

We push a little further the study of two recent characterizations of almost perfect nonlinear (APN) functions. We state open problems about them, and we revisit in their perspective a well-known result from Dobbertin on APN exponents. This leads us to a new result about APN power functions and more general APN polynomials with coefficients in a subfield \begin{document}$ \mathbb{F}_{2^k} $\end{document} , which eases the research of such functions. It also allows to construct automatically many differentially uniform functions from them (this avoids calculations for proving their differential uniformity as done in a recent paper, which are tedious and specific to each APN function). In a second part, we give simple proofs of two important results on Boolean functions, one of which deserves to be better known but needed clarification, while the other needed correction.

This paper constructs a new local to global principle for expected values over free Z -modules of finite rank. In our strategy we use the same philosophy as Ekedahl's Sieve for densities, later extended and improved by Poonen and Stoll in their local to global principle for densities. We show that under some additional hypothesis on the system of p-adic subsets used in the principle, one can use p-adic measures also when one has to compute expected values (and not only densities). Moreover, we show that our additional hypotheses are sharp, in the sense that explicit counterexamples exist when any of them is missing. In particular, a system of p-adic subsets that works in the Poonen and Stoll principle is not guaranteed to work when one is interested in expected values instead of densities. Finally, we provide both new applications of the method, and immediate proofs for known results.

The converse of the Borel–Cantelli Lemma states that if { A i } i = 1 ∞ is a sequence of independent events such that ∑ P ( A i ) = ∞ , then almost surely infinitely many of these events will occur. Erdős and Renyi proved that it is sufficient to weaken the condition of independence to pairwise independence. Later, several other weakenings of the condition appeared in the literature. The aim of this paper is to provide a collection of conditions, all of which imply that almost surely infinitely many of the events occur, and determine the complete implicational relationship between them. Many of these results are known, or follow from known results, however, they are not widely known among non-specialists. Yet, the results can be extremely useful for areas outside of probability theory, as evidenced by the original motivation of this paper emerging from infinite combinatorics. Our proofs are aimed to be accessible to a general mathematical audience.

Comunicació presentada al AFRICACRYPT 2020: 12th International Conference on Cryptology in Africa, celebrat del 20 al 22 de juliol de 2021 al Caire, Egipte. This paper constructs unbounded simulation sound proofs for boolean circuit satisfiability under standard assumptions with proof size O(n+d) bilinear group elements, where d is the depth and n is the input size of the circuit. Our technical contribution is to add unbounded simulation soundness to a recent NIZK of González and Ràfols (ASIACRYPT’19) with very small overhead. Our new scheme can be used to construct the most efficient Signature-of-Knowledge based on standard assumptions that also can be composed universally with other cryptographic protocols/primitives. Karim Baghery was supported by CyberSecurity Research Flanders with reference number VR20192203.

Chapter 15 discusses the nature of proof and theorem proving and considers the history of theorem proving from the development of the Logic Theorist theorem prover in 1956. We discuss automated and interactive theorem provers; the nature of mathematical proof and formal mathematical proof; and a selection of existing theorem provers.

We provide a semi-grammatical description of the set of normal proofs of positive formulae in minimal predicate logic, i.e. a grammar that generates a set of schemes, from each of which we can produce a finite number of normal proofs. This method is complete in the sense that each normal proof-term of the formula is produced by some scheme generated by the grammar. As a corollary, we get a similar description of the set of normal proofs of positive formulae for a large class of theories including simple type theory and System F.

In this note, we point out that Theorem 3 (a version of Egoroff's theorem for monotone set-valued measures) shown in the paper “Lusin's theorem for monotone set-valued measures on topological spaces” (Fuzzy Sets and Systems 364 (2019) 111-123) is not valid, and we present two revised versions. We also point out that the proofs of Lemma 2 and Theorem 1 are defective, thus the truth of their conclusions cannot be affirmed. Thereby, an open problem for the characteristics of monotone measures is raised.

We provide visual proofs about the sums of entries in odd-indexed polygonal arrays generalizing the classic visual proof about sums of odd numbers.

The hypercube cut number S ( d ) is the minimum number of hyperplanes in the d -dimensional Euclidean space that slice all the edges of the d -cube. The determination of S ( d ) in dimensions 5, 6, and 7, is one of the Victor Klee’s unresolved problems presented in one of his invited talks on problems from discrete geometry. The value of S ( d ) is unknown for d ≥ 7 , but for d ≤ 3 it is trivial to show S ( d ) = d . In the late nineteen eighties, Emamy-K has shown S ( 4 ) = 4 via two different proofs. More than a decade later, Sohler and Ziegler obtained a computational proof of S ( 5 ) = 5 that took about two months of CPU computing time. From S ( 5 ) = 5 it can be verified that S ( 6 ) = 5 . A short mathematical proof for d = 5 remains to be a challenging problem that also leads one to the insight of the still open 7-dimensional problem. In this article we present a vertex coloring approach on the hypercube that gives a simplified proof for d = 4 and also helps toward a short mathematical proof for d = 5 , free of computer computations.

У цій публікації наведено нові доведення двох комбінаторних тотожностей. Часткові випадки цих тотожностей містять числа та многочлени Нараяна і використовуються, зокрема, у класичній теорії інваріантів та дискретній математиці. Одна із доведених нами тотожностей є узагальненням задачі Стенлі. Хоча існує велика кількість методів генерування нових комбінаторних тотожностей, на жаль, не існує єдиного універсального методу, який дозволив би довести будь-яку комбінатрону тотожність. У сімдесятих роках минулого століття Георгієм Єгоричевим було розроблено декілька нових методів обчислення комбінаторних сум. У цій статті ми використовуємо один з методів Єгоричева - метод лишків (коефіцієнтів).

The aim of this paper is to obtain three types of expressions for calculating the probability of implementing palindromic digit combinations on a finite equally possible combination of zeros and ones. When calculating the probability of implementation of palindromic digit combinations, the classical definition of probability is applied. The main results of the paper are formulated in the form of three theorems. Moreover, the consequences of these theorems and typical examples of calculating the probability of implementing palindromic digit combinations in a data string of binary code are considered. All formulated theorems and their consequences are accompanied by proofs. The obtained numerical results of the paper can be used in the analysis of numerical computer data written as a binary code string in BIN format files. It should also be noted that the combinatorial expressions described in the article for calculating the number of palindromic combinations of digits in the binary number system can be used in number theory and in various branches of computer science. The development of these results from the point of view of obtaining an expression for calculating the number of palindromic combinations of digits in the binary number system contained in two-dimensional data arrays is also of immediate theoretical and practical interest. However, these results are not presented in this work, but they can be considered in subsequent publications.

In this paper we formulate combinatorial identities that give representation of positive integers as linear combination of even powers of 2 with binomial coefficients. We present side by side combinatorial as well as computer generated proofs using the Wilf-Zeilberger(WZ) method.

Let $q\in\mathbb{C}$, let \[a=\begin{pmatrix} 1&0\\1&1\end{pmatrix},\quad b_q=\begin{pmatrix} 1&q\\0&1\end{pmatrix},\] and let $G_q27$, we prove that the lower density of denominators $r\in \mathbb{N}$ for which $G_{s/r}$ is non-free has a lower bound \[ 1- \left(1-\frac{11}{s}\right) \prod_{n=1}^\infty \left(1-\frac{4}{s^{2^n-1}}\right). \] Finally, we show that for a fixed $s$, there are arbitrarily long sequences of consecutive denominators $r$ such that $G_{s/r}$ is non-free. The proofs of some of the results are computer assisted, and Mathematica code has been provided together with suitable documentation., Comment: 26 pages. To appear in the Michigan Mathematical Journal

New and elementary proofs for three cubic q-series transformations due to Gasper and Rahman (Am Math Soc 312:1, 1989; Can J Math 42, 1990) are presented by means of the Abel lemma on summation by parts. As consequences, q-analogues for Gosper’s two summation formulae of $$_3F_2(3/4)$$ -series are established.

We give a transport proof of a discrete version of the displacement convexity of entropy on integers (Z), and get, as a consequence, two discrete forms of the Prekopa-Leindler Inequality : the Four Functions Theorem of Ahlswede and Daykin on the discrete hypercube [1] and a recent result on Z due to Klartag and Lehec [16].

This article is motivated by seeking lower bounds on OBDD(∧, w, r) refutations, namely, OBDD refutations that allow weakening and arbitrary reorderings. We first work with 1 - NBP ∧ refutations based on read-once nondeterministic branching programs. These generalize OBDD(∧, r) refutations. There are polynomial size 1 - NBP(∧) refutations of the pigeonhole principle, hence 1-NBP(∧) is strictly stronger than OBDD}(∧, r). There are also formulas that have polynomial size tree-like resolution refutations but require exponential size 1-NBP(∧) refutations. As a corollary, OBDD}(∧, r) does not simulate tree-like resolution, answering a previously open question. The system 1-NBP(∧, ∃) uses projection inferences instead of weakening. 1-NBP(∧, ∃ k is the system restricted to projection on at most k distinct variables. We construct explicit constant degree graphs G n on n vertices and an ε > 0, such that 1-NBP(∧, ∃ ε n ) refutations of the Tseitin formula for G n require exponential size. Second, we study the proof system OBDD}(∧, w, r ℓ ), which allows ℓ different variable orders in a refutation. We prove an exponential lower bound on the complexity of tree-like OBDD(∧, w, r ℓ ) refutations for ℓ = ε log n , where n is the number of variables and ε > 0 is a constant. The lower bound is based on multiparty communication complexity.

In this paper, we shall give another proof of the faithfulness of Blass translation (for short, B-translation) of the propositional fragment $$\mathbf{L}_1$$ of Leśniewski’s ontology in the modal logic $$\mathbf{K}$$ by means of Hintikka formula. And we extend the result to von Wright-type deontic logics, i.e., ten Smiley-Hanson systems of monadic deontic logic. As a result of observing the proofs we shall give general theorems on the faithfulness of B-translation with respect to normal modal logics complete to certain sets of well-known accessibility relations with a restriction that transitivity and symmetry are not set at the same time. As an application of the theorems, for example, B-translation is faithful for the provability logic $$\mathbf{PrL}$$ (= $$\mathbf{GL}$$ ), that is, $$\mathbf{K}$$ $$+$$ $$\Box (\Box \phi \supset \phi ) \supset \Box \phi $$ . The faithfulness also holds for normal modal logics, e.g., $$\mathbf{KD}$$ , $$\mathbf{K4}$$ , $$\mathbf{KD4}$$ , $$\mathbf{KB}$$ . We shall conclude this paper with the section of some open problems and conjectures.

The problem of finding, among the Euler parallelepipeds, one with an integer spatial diagonal, called the perfect cuboid problem, is one of the unsolved mathematical problems from the section of number theory. This article provides mathematical proof of the impossibility of the existence of the perfect cuboide among all possible Euler parallelepipeds. A mathematical justification for an equivalence of the problem of doubling a cube and the problem of constructing a perfect cuboid is also given.

This paper introduces a natural deduction calculus for intuitionistic logic of belief$$\mathsf {IEL}^{-}$$ IEL - which is easily turned into a modal$$\lambda $$ λ -calculus giving a computational semantics for deductions in $$\mathsf {IEL}^{-}$$ IEL - . By using that interpretation, it is also proved that $$\mathsf {IEL}^{-}$$ IEL - has good proof-theoretic properties. The correspondence between deductions and typed terms is then extended to a categorical semantics for identity of proofs in $$\mathsf {IEL}^{-}$$ IEL - showing the general structure of such a modality for belief in an intuitionistic framework.

$\{log\}$ (‘setlog’) is a satisfiability solver for formulas of the theory of finite sets and finite set relation algebra (FS&RA). As such, it can be used as an automated theorem prover for this theory. $\{log\}$ is able to automatically prove a number of FS&RA theorems, but not all of them. Nevertheless, we have observed that many theorems that $\{log\}$ cannot automatically prove can be divided into a few subgoals automatically dischargeable by $\{log\}$. The purpose of this work is to present a prototype interactive theorem prover (ITP), called $\{log\}$-ITP, providing evidence that a proper integration of $\{log\}$ into world-class ITP’s can deliver a great deal of proof automation concerning FS&RA. An empirical evaluation based on 210 theorems from the TPTP and Coq’s SSReflect libraries shows a noticeable reduction in the size and complexity of the proofs with respect to Coq.

Separation logic (SL) is a logical formalism for reasoning about programs that use pointers to mutate data structures. It is successful for program verification as an assertion language to state properties about memory heaps using Hoare triples. Most of the proof systems and verification tools for ${\textrm{SL}}$ focus on the decidable but rather restricted symbolic heaps fragment. Moreover, recent proof systems that go beyond symbolic heaps are purely syntactic or labelled systems dedicated to some fragments of ${\textrm{SL}}$ and they mainly allow either the full set of connectives, or the definition of arbitrary inductive predicates, but not both. In this work, we present a labelled proof system, called ${\textrm{G}_{\textrm{SL}}}$, that allows both the definition of cyclic proofs with arbitrary inductive predicates and the full set of SL connectives. We prove its soundness and show that we can derive in ${\textrm{G}_{\textrm{SL}}}$ the built-in rules for data structures of another non-cyclic labelled proof system and also that ${\textrm{G}_{\textrm{SL}}}$ is strictly more powerful than that system.

In this paper, we study the Hormander multiplier theorem for multilinear operators. We generalize the result of Tomita (J Funct Anal 259(8):2028–2044, 2010) to wider target spaces and extend that of Grafakos and Van Nguyen (Monatsh Math 190(4):735–753, 2019) to multilinear operators. We indeed give two different proofs: The first proof is based on the results of Grafakos et al. (Can J Math 65(2):299–330, 2013; II J Math Soc Jpn 69(2):529–562, 2017), Grafakos and Van Nguyen (Colloq Math 144(1):1–30, 2016; Monatsh Math 190(4):735–753, 2019), Miyachi and Tomita (Rev Mat Iberoam 29(2):495–530, 2013) and for the second one we provide a new and original approach, inspired by Muscalu et al. (Acta Math 193(2):269–296, 2004). We also give an application and discuss the sharpness of the result.

Representation predicates enable data abstraction in separation logic, but when the same concrete implementation may need to be abstracted in different ways, one needs a notion of subsumption. We demonstrate function-specification subtyping, analogous to subtyping, with a subsumption rule: if \(\phi \) is a Open image in new window of \(\psi \), that is \(\phi

The ring Int(Z) of integer-valued polynomials has the two-generator property, which means that every finitely generated ideal may be generated by two elements. As the known proofs of this fact are ...

The sums of powers of the first n natural numbers represent a classical topic in mathematics, with the formula for the sum of squares known already to Archimedes in the 3rd century BCE [2] and the ...

The purpose of the paper is to study the uniqueness problem of an L function in the Selberg class sharing one or two sets with an arbitrary meromorphic function having only finitely many poles. We manipulate the notion of weighted sharing of sets to improve a result of Q.Q. Yuan, X.M. Li, and H.X. Yi [Value distribution of L-functions and uniqueness questions of F. Gross, Lith. Math. J., 58(2):249–262, 2018]. Most importantly, we have pointed out a number of logical shortcomings in the two results of P. Sahoo and S. Haldar [Results on L functions and certain uniqueness question of Gross, Lith. Math. J., 60(1):80–91, 2020]. As an attempt to rectify the results of Sahoo and Halder, we have improved them by presenting their accurate forms and proofs as far as practicable.

Navigators have been taught for centuries to estimate the location of their craft on a map from three lines of position, for redundancy. The three lines typically form a triangle, called a cocked hat. How is the location of the craft related to the triangle? For more than 80 years navigators have also been taught that, if each line of position is equally likely to pass to the right and to the left of the true location, then the likelihood that the craft is in the triangle is exactly 1/4. This is stated in numerous reputable sources, but was never stated or proved in a mathematically formal and rigorous fashion. In this paper we prove that the likelihood is indeed 1/4 if we assume that the lines of position always intersect pairwise. We also show that the result does not hold under weaker (and more reasonable) assumptions, and we prove a generalisation to $n$ lines.

Niederreiter and Halton sequences are two prominent classes of higher-dimensional sequences which are widely used in practice for numerical integration methods because of their excellent distribution qualities. In this paper we show that these sequences—even though they are uniformly distributed—fail to satisfy the stronger property of Poissonian pair correlations. This extends already established results for one-dimensional sequences and confirms a conjecture of Larcher and Stockinger who hypothesized that the Halton sequences are not Poissonian. The proofs rely on a general tool which identifies a specific regularity of a sequence to be sufficient for not having Poissonian pair correlations.

Covering rough set is a classical generalization of rough set. As covering rough set is a mathematical tool to deal with incomplete and incomplete data, it has been widely used in various fields. The aim of this paper is to extend the covering rough sets to interval neutrosophic sets, which can make multi-attribute decision making problem more tractable. Interval neutrosophic covering rough sets can be viewed as the bridge connecting Interval neutrosophic sets and covering rough sets. Firstly, the paper introduces the definition of interval neutrosophic sets and covering rough sets, where the covering rough set is defined by neighborhood. Secondly, Some basic properties and operation rules of interval neutrosophic sets and covering rough sets are discussed. Thirdly, the definition of interval neutrosophic covering rough sets are proposed. Then, some theorems are put forward and their proofs of interval neutrosophic covering rough sets also be gived. Lastly, this paper gives a numerical example to apply the interval neutrosophic covering rough sets.

This paper applies Dehornoy et al.’s Z theorem and its variant, called the compositional Z theorem, to prove confluence of Parigot’s $$\lambda \mu $$ -calculi extended by the simplification rules. First, it is proved that Baba et al.’s modified complete developments for the call-by-name and the call-by-value variants of the $$\lambda \mu $$ -calculus with the renaming rule, which is one of the simplification rules, satisfy the Z property. It gives new confluence proofs for them by the Z theorem. Secondly, it is shown that the compositional Z theorem can be applied to prove confluence of the call-by-name and the call-by-value $$\lambda \mu $$ -calculi with both simplification rules, the renaming and the $$\mu \eta $$ -rules, whereas it is hard to apply the ordinary parallel reduction technique or the original Z theorem by one-pass definition of mappings for these variants.

In a recent paper, Baker and Kong have studied the Hausdorff dimension of the intersection of Cantor sets with their translations. We extend their results to more general Cantor sets. The proofs rely on the frequencies of digits in unique expansions in non-integer bases. In relation with this, we introduce a practical method to determine the frequency of any given finite block in Thue--Morse type sequences.

This document serves as an arXiv entry point for the appendix to the paper [13] (the ancillary file e6_proof.pdf -- ``Proof of the tree module property for exceptional representations of the quiver $\widetilde{\mathbb{E}}_6$'') and the appendix to the paper [12] (the ancillary file d6_proof.pdf -- ``Proof of the tree module property for exceptional representations of the quiver $\widetilde{\mathbb{D}}_6$''). The ancillary files contain the computer generated part of the proofs of the main results in [13] respectively [12], giving a complete and general list of tree representations corresponding to exceptional modules over the path algebra of the canonically oriented Euclidean quiver $\widetilde{\mathbb{E}}_6$, respectively $\widetilde{\mathbb{D}}_6$. The proofs (involving induction and symbolic computation with block matrices) were partially generated by a purposefully developed computer software, outputting in a detailed step-by-step fashion as if written ``by hand''. We also give here a short theoretical introduction and an overview of the computational method used to prove the formulas given in the papers [13] and [12].

We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi [26], where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs whose lines are circuits from restricted boolean circuit classes. Essentially all of the subsystems considered in this paper can simulate the well-studied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). Our main contributions are two general methods of converting certain algebraic lower bounds into proof complexity ones. Both require stronger arithmetic lower bounds than common, which should hold not for a specific polynomial but for a whole family defined by it. These may be likened to some of the methods by which Boolean circuit lower bounds are turned into related proof-complexity ones, especially the "feasible interpolation" technique. We establish algebraic lower bounds of these forms for several explicit polynomials, against a variety of classes, and infer the relevant proof complexity bounds. These yield separations between IPS subsystems, which we complement by simulations to create a partial structure theory for IPS systems. Our first method is a functional lower bound, a notion of Grigoriev and Razborov [25], which is a function [EQUATION] {0, 1}n → F such that any polynomial f agreeing with [EQUATION] on the boolean cube requires large algebraic circuit complexity. We develop functional lower bounds for a variety of circuit classes (sparse polynomials, depth-3 powering formulas, read-once algebraic branching programs and multilinear formulas) where [EQUATION] equals [EQUATION] for a constant-degree polynomial p depending on the relevant circuit class. We believe these lower bounds are of independent interest in algebraic complexity, and show that they also imply lower bounds for the size of the corresponding IPS refutations for proving that the relevant polynomial p is non-zero over the boolean cube. In particular, we show super-polynomial lower bounds for refuting variants of the subset-sum axioms in these IPS subsystems. Our second method is to give lower bounds for multiples, that is, to give explicit polynomials whose all (non-zero) multiples require large algebraic circuit complexity. By extending known techniques, we give lower bounds for multiples for various restricted circuit classes such sparse polynomials, sums of powers of low-degree polynomials, and roABPs. These results are of independent interest, as we argue that lower bounds for multiples is the correct notion for instantiating the algebraic hardness versus randomness paradigm of Kabanets and Impagliazzo [31]. Further, we show how such lower bounds for multiples extend to lower bounds for refutations in the corresponding IPS subsystem.

The number of linear proofs steps for some sets of formulas is compared in the folowing systems of propositional calculus: PK – seguent system with cut rule, PK— - the same system without cut rule, SPK – the same system with substitution rule, QPK – the same system with quantifier rules. The number of steps of tree-like proofs in the same systems for some considered set of formulas is compared from Alessandra Carbone in [1] and some distinctive property of the system QPK is revealed: QPK has an exponential speed-up over the systems SPK and PK, which, in their turn, have an exponential speed-up over the system PK—. This result drew the heavy interest for the study of the system QPK. In this work for linear proofs steps in the same systems the other relations are received: it is showed that the system QPK has no preference over the system SPK, it is showed also that for the considered formula sets the system PK has no preference over the system PK—, which, in its turn, has no preference over the monotone system PMon. It is proved also, that the same results are reliable for some other sets of formulas and for other systems as well.

In 1986, Proinov published an explicit lower bound for the diaphony of finite and infinite sequences of points contained in the d−dimensional unit cube [Proinov, P. D.:On irregularities of distribution, C. R. Acad. Bulgare Sci. 39 (1986), no. 9, 31–34]. However, his widely cited paper does not contain the proof of this result but simply states that this will appear elsewhere. To the best of our knowledge, this proof was so far only available in a monograph of Proinov written in Bulgarian [Proinov, P. D.: Quantitative Theory of Uniform Distribution and Integral Approximation, University of Plovdiv, Bulgaria (2000)]. The first contribution of our paper is to give a self contained version of Proinov’s proof in English. Along the way, we improve the explicit asymptotic constants implementing recent, and corrected results of [Hinrichs, A.—Markhasin, L.: On lower bounds for the ℒ2 -discrepancy, J. Complexity 27 (2011), 127–132.] and [Hinrichs, A.—Larcher, G.: An improved lower bound for the ℒ2 -discrepancy, J. Complexity 34 (2016), 68–77]. (The corrections are due to a note in [Hinrichs, A.—Larcher, G. An improved lower bound for the ℒ2 -discrepancy, J. Complexity 34 (2016), 68–77].) Finally, as a main result, we use the method of Proinov to derive an explicit lower bound for the dyadic diaphony of finite and infinite sequences in a similar fashion.

We study a guessing game where Alice holds a discrete random variable $X$ , and Bob tries to sequentially guess its value. Before the game begins, Bob can obtain side-information about $X$ by asking an oracle, Carole, any binary question of his choosing. Carole’s answer is however unreliable, and is incorrect with probability $\epsilon $ . We show that Bob should always ask Carole whether the index of $X$ is odd or even with respect to a descending order of probabilities – this question simultaneously minimizes all the guessing moments for any value of $\epsilon $ . In particular, this result settles a conjecture of Burin and Shayevitz. We further consider a more general setup where Bob can ask a multiple-choice $M$ -ary question, and then observe Carole’s answer through a noisy channel. When the channel is completely symmetric, i.e., when Carole decides whether to lie regardless of Bob’s question and has no preference when she lies, a similar question about the ordered index of $X$ (modulo $M$ ) is optimal. Interestingly however, the problem of testing whether a given question is optimal appears to be generally difficult in other symmetric channels. We provide supporting evidence for this difficulty, by showing that a core property required in our proofs becomes NP-hard to test in the general $M$ -ary case. We establish this hardness result via a reduction from the problem of testing whether a system of modular difference disequations has a solution, which we prove to be NP-hard for $M\geq 3$ .

Following Newman (2010), we initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph. The tester is given free access to a base graph G = ([ n ], E ) and oracle access to a function f : E → {0, 1} that represents a subgraph of G . The tester is required to distinguish between subgraphs that possess a predetermined property and subgraphs that are far from possessing this property. We focus on bounded-degree base graphs and on the relation between testing graph properties in the subgraph model and testing the same properties in the bounded-degree graph model. We identify cases in which testing is significantly easier in one model than in the other as well as cases in which testing has approximately the same complexity in both models. Our proofs are based on the design and analysis of efficient testers and on the establishment of query-complexity lower bounds.

Szemeredi's Regularity Lemma is a very useful tool of extremal combinatorics. Recently, several refinements of this seminal result were obtained for special, more structured classes of graphs. We survey these results in their rich combinatorial context. In particular, we stress the link to the theory of (structural) sparsity, which leads to alternative proofs, refinements and solutions of open problems. It is interesting to note that many of these classes present challenging problems. Nevertheless, from the point of view of regularity lemma type statements, they appear as ``gentle'' classes.

In this paper we present a short proof of the following classification Theorem for g −harmonic functions in half-spaces. Assume that u is a nonnegative solution to Δgu = 0 in {xn > 0} that continuously vanishes on the flat boundary {xn = 0}. Then, modulo normalization, u(x) = xn in {xn ≥ 0}. Our proof depends on a recent quantitative version of the Hopf-Oleinik Lemma proven by the authors in Braga and Moreira (Adv. Math.334, 184–242, 2018). Moreover, in this paper, we show how to adapt the proofs in the literature to extend Carleson Estimate, Boundary Harnack Inequality and Schwartz Reflection Principle to the context of nonnegative g −harmonic functions. These results are also ingredients for the proof of the main result.

From the early 1960s to the early 1970s, there was much activity leading up to a proof that if the group ring R[G] is right self-injective, then G is finite. Unfortunately, it is difficult to find this fact both stated and proven in print and in full generality. This article presents new renditions of the main proofs, and chronicles what the author learned while sorting out the literature for this period.

The proofs of Gödel (1931), Rosser (1936), Kleene (first 1936 and second 1950), Chaitin (1970), and Boolos (1989) for the first incompleteness theorem are compared with each other, especially from the viewpoint of the second incompleteness theorem. It is shown that Gödel’s (first incompleteness theorem) and Kleene’s first theorems are equivalent with the second incompleteness theorem, Rosser’s and Kleene’s second theorems do deliver the second incompleteness theorem, and Boolos’ theorem is derived from the second incompleteness theorem in the standard way. It is also shown that none of Rosser’s, Kleene’s second, or Boolos’ theorems is equivalent with the second incompleteness theorem, and Chaitin’s incompleteness theorem neither delivers nor is derived from the second incompleteness theorem. We compare (the strength of) these six proofs with one another.

The known proofs of MA ⊆ PP incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which MA-TIME ( t ) ⊈ P-TIME ( o ( t 2 )). We also show that 2-sided-error Merlin–Arthur games can be simulated by 1-sided-error Arthur–Merlin games with quadratic overhead. We also present a simple, query complexity based proof (provided by Mika Göös) that there is an oracle relative to which MA ⊈ NP BPP (which was previously known to hold by a proof using generics).

In order to give a unified generalization of the BW inequality and the DDVV inequality, Lu and Wenzel proposed three Conjectures 1, 2, 3 and an open Question 1 in 2016. In this paper we discuss further these conjectures and put forward several new conjectures which will be shown equivalent to Conjecture 2. In particular, we prove Conjecture 2 and hence all conjectures in some special cases. For Conjecture 3, we obtain a bigger upper bound $2+\sqrt{10}/2$, and we also give a weaker answer for the more general Question 1. In addition, we obtain some new simple proofs of the complex BW inequality and the condition for equality., 31 pages

We consider two examples of a fully decodable combinatorial encoding of Bernoulli schemes: the encoding via Weyl simplices and the much more complicated encoding via the RSK (Robinson-Schensted-Knuth) correspondence. In the first case, decodability is quite a simple fact, while in the second case, this is a nontrivial result obtained by D. Romik and P. Sniady and based on [2], [12], and other papers. We comment on the proofs from the viewpoint of the theory of measurable partitions; another proof, using representation theory and generalized Schur-Weyl duality, will be presented elsewhere. We also study a new dynamics of Bernoulli variables on P-tableaux and find the limit 3D-shape of these tableaux.

الملخص تعد مشکلة التفاف(1)detour البراهين في أنسقة الاستنباط الطبيعى مشکلة في غاية الأهمية، وهى مشکلة لا نجد مثيلا لها في الأنسقة الأکسيوماتيکية. وهى تعنى، على نحو مبسط، تکرار خطوات البرهان، وهو أمر معيب من ناحية اشتقاق البراهين. لقد أدرک جنتسن G. Gentzen صاحب أول نسق في الاستنباط الطبيعى تلک المشکلة، وهو قد استطاع حلها بالنسبة لأنسقة الاستنباط الطبيعى الحدسية دون الکلاسيکية، من خلال مبرهنته على معيارية Normalization / Haupstaz البراهين الحدسية، أى البرهنة على إمکانية حذف التفاف البراهين. ويعود الفضل إلى داج برافيتس D. Prawitz فى وضع أول برهان على معيارية براهين منطق الاستنباط الطبيعى الکلاسيکى من خلال استخدام قاعدة البرهان غير المباشر. في هذا البحث سوف نتساءل عن قدرة تلک القاعدة على ذلک حقا، وإمکانية وجود قاعدة بديلة الکلمات المفتاحية: برهان غير مباشر- التفاف البراهين- استنباط طبيعى-منطق حدسى- قانون بيرس [Abstract: The problem of the detour of proofs in natural deduction systems is a serious problem. We can not find a counterpart for this problem in axiomatic systems. It means, roughly speaking, repetition to the lines or steps of proof. This is a fault from a derivative point of view. G. Gentzen, the first logician to put a calculus for natural deduction , knew this problem very well, he even could solve it in respect to intuitive natural deductions systems but not to classical ones. He solved that problem by his Haupstaz or Normalization theorem for intuitive proofs, i.e. proving the possibility of eliminating the detours in proofs. It was Dag Prawitz who put the first proof of the normalization of proofs in natural deduction for classical systems by indirect proof rule. In this paper, I shall scrutinize the ability of that rule of doing what wanted from it and if there is an alternative one for it.]

Log-concavity [log-convexity] and their various properties play an increasingly important role in probability, statistics, operations research and other fields. In this paper, we first establish general preservation theorems of log-concavity and log-convexity under operator $\phi \longmapsto T(\phi , \theta )=\mathbb {E}[\phi (X_\theta )]$, θ ∈ Θ, where Θ is an interval of real numbers or an interval of integers, and the random variable $X_\theta$ has a distribution function belonging to the family $\{F_\theta , \theta \in \Theta \}$ possessing the semi-group property. The proofs are based on the theory of stochastic comparisons and weighted distributions. The main results are applied to some special operators, for example, operators occurring in reliability, Bernstein-type operators and Beta-type operators. Several known results in the literature are recovered.

This paper is a condensation of my arXiv monograph entitled Schwartz “The phase transition in 5 point energy minimization”, 2016. arXiv:1610.03303, which contains a complete proof that there is a constant such that the triangular bi-pyramid is the minimizer, amongst all 5 point configurations on the sphere, with respect to the power law potential $$R_s(r)=\mathrm{sign}(s)/r^s$$, if and only if . In this paper we explain the main ideas and give proofs for some of the key lemmas.