Some Weak Forms of the Axiom of Choice Restricted to the Real Line

It is shown that AC(ℝ), the axiom of choice for families of non‐empty subsets of the real line ℝ, does not imply the statement PW(ℝ), the powerset of ℝ can be well ordered. It is also shown that (1) the statement “the set of all denumerable subsets of ℝ has size 2 ${}^{\text{ℵ}{}_{\text{0}}}$ ” is strictly weaker than AC(ℝ) and (2) each of the statements (i) “if every member of an infinite set of cardinality 2 ${}^{\text{ℵ}{}_{\text{0}}}$ has power 2 ${}^{\text{ℵ}{}_{\text{0}}}$ , then the union has power 2 ${}^{\text{ℵ}{}_{\text{0}}}$ ” and (ii) “ℵ(2 ${}^{\text{ℵ}{}_{\text{0}}}$ ) ≠ ℵ_ω” (ℵ(2 ${}^{\text{ℵ}{}_{\text{0}}}$ ) is Hartogs' aleph, the least ℵ not ≤ 2 ${}^{\text{ℵ}{}_{\text{0}}}$ ), is strictly weaker than the full axiom of choice AC.     

Universal bounds for global solutions of a forced porous medium equation

We show that in a smooth bounded domain $\text{Ω⊂}\text{R}{}^{\mathrm{n}}$, n⩾2, all global nonnegative solutions of u_t−Δu^m=u^p with zero boundary data are uniformly bounded in $\text{Ω×(τ,∞)}$ by a constant depending on $\text{Ω,p}$ and τ but not on u₀, provided that 1<m<p<[(n+1)/(n−1)]m. Furthermore, we prove an a priori bound in $\text{L}{}^{\mathrm{\infty }}\text{(Ω×(0,∞))}$ depending on $\text{||u}{}_0\text{||}{}_{\mathrm{L\infty (\Omega )}}$ under the optimal condition 1<m<p<[(n+2)/(n−2)]m.     

On the complexity of solving quadratic Boolean systems

A fundamental problem in computer science is that of finding all the common zeros of m$m$ quadratic polynomials in n$n$ unknowns over _F2${\mathbb{F}}_2$. The cryptanalysis of several modern ciphers reduces to this problem. Up to now, the best complexity bound was reached by an exhaustive search in 4_log2n2ⁿ$4{log}_{2}n{2}^n$ operations. We give an algorithm that reduces the problem to a combination of exhaustive search and sparse linear algebra. This algorithm has several variants depending on the method used for the linear algebra step. We show that, under precise algebraic assumptions on the input system, the deterministic variant of our algorithm has complexity bounded by O(2^0.841n)$O\left(2^{0.841n}\right)$ when m=n$m=n$, while a probabilistic variant of the Las Vegas type has expected complexity O(2^0.792n)$O\left(2^{0.792n}\right)$. Experiments on random systems show that the algebraic assumptions are satisfied with probability very close to 1. We also give a rough estimate for the actual threshold between our method and exhaustive search, which is as low as 200, and thus very relevant for cryptographic applications.     

On sparse countably infinite Steiner triple systems

We give a general construction for Steiner triple systems on a countably infinite point set and show that it yields 2 ${}^{\text{?}{}_{\text{0}}}$ nonisomorphic systems all of which are uniform and r‐sparse for all finite r?4. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 115–122, 2010     

On the number of groups of a given order

Letting G(n) denote the number of nonisomorphic groups of order n, it is shown that for square-free n, G(n) ≤ ?(n) and G(n) ≤ (log n)^c on a set of positive density. Letting F_k(x) denote the number of n ≤ x for which G(n) = k, it is shown that $\text{F}{}_2\text{(x) =}\text{O(x(}\text{log}{}_4\text{x)}\text{(}\text{log}{}_3\text{x)}{}^2\text{)}$, where log_rx denotes the r-fold iterated logarithm.     

On the qth convergence exponent of entire functions

In this paper we obtain a growth relation for entire functions of qth order with respect to the distribution of its zeros. We also derive certain relations between the qth convergence exponents of two or more entire functions. The most striking result of the paper is: If f(z) has at least one zero, then

$\text{lim sup}\text{r→∞}\text{log n}\text{(r)}\text{log}{}^{\mathrm{[q+1]}}{}_{\mathrm{r}}\text{=?(q)}$

, where n(r) is the number of zeros of f(z) in $\text{¦}\text{z}\text{¦ ? r}$ and

$\text{?(q)=g.l.b.}\text{α:α>0 and}\text{∑}\text{∞}\text{n=1}\text{(log}{}^{\mathrm{[q]}}\text{r}{}_{\mathrm{n}}\text{)}{}^{\mathrm{-\alpha }}\text{<∞}$

.     

Periodic oscillations of coefficients of power series that satisfy functional equations

It is shown that the coefficients a_n of the power series f(z) = ∑^∞_n=1a_nzⁿ which satisfies the functional equation

$\text{f(z)=z+f(z}{}^2\text{+z}{}^3\text{)}$

display periodic oscillations; $\text{a}{}_{\mathrm{n}}\text{～ (}\text{ø}{}^{\mathrm{n}}\text{n}\text{) u(}\text{log}\text{n}$ as n → ∞, where $\text{ø =}\text{(1 + 5}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}\text{2}$ and u(x) is a positive, nonconstant, continuous function which is periodic with period log(4 ? ø). Similar results are obtained for a wide class of power series that satisfy similar functional equations. Power series of these types are of interest in combinatorics and computer science since they often represent generating functions. For example, the nth coefficient of the power series satisfying (1) enumerates 2, 3-trees with n leaves.     

Trace formulas for a class of Toeplitz-like operators II

Let P_T denote the orthogonal projection of L²(R¹, dΔ) onto the space of entire functions of exponential type ? T which are square summable on the line with respect to the measure $\text{dΔ(γ) = ¦ h(γ)¦}{}^2\text{dγ}$, and let G denote the operator of multiplication by a suitably restricted complex valued function g. It is shown that if $\text{(γ}{}^2\text{+ 1)}{}^{\mathrm{?1}}\text{log}\text{¦ h(γ)¦}$ is summable, if $\text{¦ h ¦}{}^{\mathrm{?2}}$ is locally summable, and if $\text{h}\text{h}{}^{\mathrm{\#}}$ belongs to the span in L^∞ of e^?iyTH^∞:T ? 0, in which h is chosen to be an outer function and h^#(γ) agrees with the complex conjugate of h(γ) on the line, then

$\text{lim trace}\text{T↑∞}\text{{(P}{}_{\mathrm{T}}\text{GP}{}_{\mathrm{T}}\text{)}{}^{\mathrm{n}}\text{? P}{}_{\mathrm{T}}\text{G}{}^{\mathrm{n}}\text{P}{}_{\mathrm{T}}\text{}}$

exists and is independent of h for every positive integer n. This extends the range of validity of a formula due to Mark Kac who evaluated this limit in the special case h = 1 using a different formalism. It also extends earlier results of the author which were established under more stringent conditions on h. The conclusions are based in part upon a preliminary study of a more general class of projections.     

Radial bounds for perturbations of elliptic operators

Elliptic operators $\text{A = ∑}{}_{\mathrm{¦\alpha ¦\; ?\; m}}\text{b}{}_{\mathrm{\alpha }}\text{(x) D}{}^{\mathrm{\alpha }}$, α a multi-index, with leading term positive and constant coefficient, and with lower order coefficients defined on $\text{R}{}^{\mathrm{<mi\; mathvariant="italic"\; is="true">n</mi>}}$ or a quotient space $\text{R}{}^{\mathrm{n}}\text{R}{}^{\mathrm{n}}\text{U}{}_{\mathrm{\alpha }}\text{, U}{}_{\mathrm{\alpha }}\text{? R}{}^{\mathrm{n}}$ are considered. It is shown that the L^p-spectrum of A is contained in a “parabolic region” Ω of the complex plane enclosing the positive real axis, uniformly in p. Outside Ω, the kernel of the resolvent of A is shown to be uniformly bounded by an L¹ radial convolution kernel. Some consequences are: A can be closed in all L^p (1 ? p ? ∞), and is essentially self-adjoint in L² if it is symmetric; A generates an analytic semigroup e^?tA in the right half plane, strongly L^p and pointwise continuous at t = 0. A priori estimates relating the leading term and remainder are obtained, and summability $\text{φ(εA)?→}{}_{\mathrm{\epsilon \; \to \; 0}}\text{φ(0) ?}$, with φ analytic, is proved for $\text{? ? L}{}^{\mathrm{p}}$, with convergence in L^p and on the Lebesgue set of ?. More comprehensive summability results are obtained when A has constant coefficients.     

On graphs which contain all small trees

We investigate those graphs G_n with the property that any tree on n vertices occurs as subgraph of G_n. In particular, we consider the problem of estimating the minimum number of edges such a graph can have. We show that this number is bounded below and above by $\text{1}\text{2}\text{n}\text{log}\text{n}$ and $\text{n}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>log\; log</mtext><mtext>\; n</mtext>}}$, respectively.     

Sobolev inequalities with remainder terms

The usual Sobolev inequality in $\text{R}$ⁿ, n ? 3, asserts that , with S_n being the sharp constant. This paper is concerned, instead, with functions restricted to bounded domains Ω ? $\text{R}$ⁿ. Two kinds of inequalities are established: (i) If ? = 0 on ?Ω, then with $\text{p =}\text{2}{}^1\text{2}$ and with $\text{q =}\text{n}\text{(n ? 1)}$. (ii) If ? ≠ 0 on ?Ω, then with $\text{q =}\text{2(n ? 1)}\text{(n ? 2)}$. Some further results and open problems in this area are also presented.