Diagonalization in proof complexity

Jan Krajíček

Displaying similar documents to “Diagonalization in proof complexity”

On a number theoretic conjecture on positive integral points in a 5-dimensional tetrahedron and a sharp estimate of the Dickman–De Bruijn function

Ke-Pao Lin, Xue Luo, Stephen S.-T. Yau, Huaiqing Zuo (2014)

Journal of the European Mathematical Society

Similarity:

It is well known that getting the estimate of integral points in right-angled simplices is equivalent to getting the estimate of Dickman-De Bruijn function $ψ (x, y)$ which is the number of positive integers $\leq x$ and free of prime factors $> y$ . Motivating from the Yau Geometry Conjecture, the third author formulated the Number Theoretic Conjecture which gives a sharp polynomial upper estimate that counts the number of positive integral points in n-dimensional ( $n \geq 3$ ) real right-angled simplices. In this...

Selection principles and upper semicontinuous functions

Masami Sakai (2009)

Colloquium Mathematicae

Similarity:

In connection with a conjecture of Scheepers, Bukovský introduced properties wQN* and SSP* and asked whether wQN* implies SSP*. We prove it in this paper. We also give characterizations of properties S₁(Γ,Ω) and $S_{f i n} (Γ, Ω)$ in terms of upper semicontinuous functions

On coarse embeddability into $ℓ_{p}$ -spaces and a conjecture of Dranishnikov

Piotr W. Nowak (2006)

Fundamenta Mathematicae

Similarity:

We show that the Hilbert space is coarsely embeddable into any $ℓ_{p}$ for 1 ≤ p ≤ ∞. It follows that coarse embeddability into ℓ₂ and into $ℓ_{p}$ are equivalent for 1 ≤ p < 2.

The generalized Hodge and Bloch conjectures are equivalent for general complete intersections

Claire Voisin (2013)

Annales scientifiques de l'École Normale Supérieure

Similarity:

We prove that Bloch’s conjecture is true for surfaces with $p_{g} = 0$ obtained as $0$ -sets $X_{σ}$ of a section $σ$ of a very ample vector bundle on a variety $X$ with “trivial” Chow groups. We get a similar result in presence of a finite group action, showing that if a projector of the group acts as $0$ on holomorphic $2$ -forms of $X_{σ}$ , then it acts as $0$ on $0$ -cycles of degree $0$ of $X_{σ}$ . In higher dimension, we also prove a similar but conditional result showing that the generalized Hodge conjecture for general $X_{σ}$ ...

Lower semicontinuous envelopes in $W^{1, 1} \times L^{p}$

Ana Margarida Ribeiro, Elvira Zappale (2014)

Banach Center Publications

Similarity:

The lower semicontinuity of functionals of the type $\int_{Ω} f (x, u, v, \nabla u) d x$ with respect to the $(W^{1, 1} \times L^{p})$ -weak* topology is studied. Moreover, in absence of lower semicontinuity, an integral representation in $W^{1, 1} \times L^{p}$ for the lower semicontinuous envelope is also provided.

On a conjecture of Dekking : The sum of digits of even numbers

Iurie Boreico, Daniel El-Baz, Thomas Stoll (2014)

Journal de Théorie des Nombres de Bordeaux

Similarity:

Let $q \geq 2$ and denote by $s_{q}$ the sum-of-digits function in base $q$ . For $j = 0, 1, \dots, q - 1$ consider $# {0 \leq n < N : s_{q} (2 n) \equiv j (mod q)} .$ In 1983, F. M. Dekking conjectured that this quantity is greater than $N / q$ and, respectively, less than $N / q$ for infinitely many $N$ , thereby claiming an absence of a drift (or Newman) phenomenon. In this paper we prove his conjecture.

Lower bounds for the largest eigenvalue of the gcd matrix on ${1, 2, \dots, n}$

Jorma K. Merikoski (2016)

Czechoslovak Mathematical Journal

Similarity:

Consider the $n \times n$ matrix with $(i, j)$ ’th entry $gcd (i, j)$ . Its largest eigenvalue $λ_{n}$ and sum of entries $s_{n}$ satisfy $λ_{n} > s_{n} / n$ . Because $s_{n}$ cannot be expressed algebraically as a function of $n$ , we underestimate it in several ways. In examples, we compare the bounds so obtained with one another and with a bound from S. Hong, R. Loewy (2004). We also conjecture that $λ_{n} > 6 π^{- 2} n log n$ for all $n$ . If $n$ is large enough, this follows from F. Balatoni (1969).

A tight quantitative version of Arrow’s impossibility theorem

Nathan Keller (2012)

Journal of the European Mathematical Society

Similarity:

The well-known Impossibility Theorem of Arrow asserts that any generalized social welfare function (GSWF) with at least three alternatives, which satisfies Independence of Irrelevant Alternatives (IIA) and Unanimity and is not a dictatorship, is necessarily non-transitive. In 2002, Kalai asked whether one can obtain the following quantitative version of the theorem: For any $ϵ > 0$ , there exists $δ = δ (ϵ)$ such that if a GSWF on three alternatives satisfies the IIA condition and its probability of...

Upper bounds for the domination numbers of toroidal queens graphs

Christina M. Mynhardt (2003)

Discussiones Mathematicae Graph Theory

Similarity:

We determine upper bounds for $γ (Q n^{t})$ and $i (Q ₙ^{t})$ , the domination and independent domination numbers, respectively, of the graph $Q ₙ^{t}$ obtained from the moves of queens on the n×n chessboard drawn on the torus.

Characterization of the alternating groups by their order and one conjugacy class length

Alireza Khalili Asboei, Reza Mohammadyari (2016)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite group, and let $N (G)$ be the set of conjugacy class sizes of $G$ . By Thompson’s conjecture, if $L$ is a finite non-abelian simple group, $G$ is a finite group with a trivial center, and $N (G) = N (L)$ , then $L$ and $G$ are isomorphic. Recently, Chen et al. contributed interestingly to Thompson’s conjecture under a weak condition. They only used the group order and one or two special conjugacy class sizes of simple groups and characterized successfully sporadic simple groups (see Li’s PhD dissertation)....

Invariance of the parity conjecture for $p$ -Selmer groups of elliptic curves in a $D_{2 p^{n}}$ -extension

Thomas de La Rochefoucauld (2011)

Bulletin de la Société Mathématique de France

Similarity:

We show a $p$ -parity result in a $D_{2 p^{n}}$ -extension of number fields $L / K$ ( $p \geq 5$ ) for the twist $1 \oplus η \oplus τ$ : $W (E / K, 1 \oplus η \oplus τ) = {(- 1)}^{〈1 \oplus η \oplus τ, X_{p} (E / L)〉}$ , where $E$ is an elliptic curve over $K$ , $η$ and $τ$ are respectively the quadratic character and an irreductible representation of degree $2$ of $Gal (L / K) = D_{2 p^{n}}$ , and $X_{p} (E / L)$ is the $p$ -Selmer group. The main novelty is that we use a congruence result between $ε_{0}$ -factors (due to Deligne) for the determination of local root numbers in bad cases (places of additive reduction above 2 and 3). We also give applications to the $p$ -parity conjecture...

A spectral bound for graph irregularity

Felix Goldberg (2015)

Czechoslovak Mathematical Journal

Similarity:

The imbalance of an edge $e = {u, v}$ in a graph is defined as $i (e) = | d (u) - d (v) |$ , where $d (\cdot)$ is the vertex degree. The irregularity $I (G)$ of $G$ is then defined as the sum of imbalances over all edges of $G$ . This concept was introduced by Albertson who proved that $I (G) \leq 4 n^{3} / 27$ (where $n = | V (G) |$ ) and obtained stronger bounds for bipartite and triangle-free graphs. Since then a number of additional bounds were given by various authors. In this paper we prove a new upper bound, which improves a bound found by Zhou and Luo in 2008. Our bound involves...

Some remarks on α-domination

Franz Dahme, Dieter Rautenbach, Lutz Volkmann (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let α ∈ (0,1) and let $G = (V_{G}, E_{G}$ ) be a graph. According to Dunbar, Hoffman, Laskar and Markus [3] a set $D \subseteq V_{G}$ is called an α-dominating set of G, if $| N_{G} (u) \cap D | \geq α d_{G} (u)$ for all $u \in V_{G} ∖ D$ . We prove a series of upper bounds on the α-domination number of a graph G defined as the minimum cardinality of an α-dominating set of G.

Polynomial quotients: Interpolation, value sets and Waring's problem

Zhixiong Chen, Arne Winterhof (2015)

Acta Arithmetica

Similarity:

For an odd prime p and an integer w ≥ 1, polynomial quotients $q_{p, w} (u)$ are defined by $q_{p, w} (u) \equiv (u^{w} - u^{w p}) / p m o d p$ with $0 \leq q_{p, w} (u) \leq p - 1$ , u ≥ 0, which are generalizations of Fermat quotients $q_{p, p - 1} (u)$ . First, we estimate the number of elements $1 \leq u < N \leq p$ for which $f (u) \equiv q_{p, w} (u) m o d p$ for a given polynomial f(x) over the finite field $_{p}$ . In particular, for the case f(x)=x we get bounds on the number of fixed points of polynomial quotients. Second, before we study the problem of estimating the smallest number (called the Waring number) of summands needed to express each...

On Kakeya–Nikodym averages, $L^{p}$ -norms and lower bounds for nodal sets of eigenfunctions in higher dimensions

Matthew D. Blair, Christopher D. Sogge (2015)

Journal of the European Mathematical Society

Similarity:

We extend a result of the second author [27, Theorem 1.1] to dimensions $d \geq 3$ which relates the size of $L^{p}$ -norms of eigenfunctions for $2 < p < 2 (d + 1) / d - 1$ to the amount of $L^{2}$ -mass in shrinking tubes about unit-length geodesics. The proof uses bilinear oscillatory integral estimates of Lee [22] and a variable coefficient variant of an " $ϵ$ removal lemma" of Tao and Vargas [35]. We also use Hörmander’s [20] $L^{2}$ oscillatory integral theorem and the Cartan–Hadamard theorem to show that, under the assumption of nonpositive...