The Proof of a Conjecture of Additive Number Theory

The aim of this paper is to show that for any n∈N, n>3, there exist a, b∈N* such that n=a+b, the “lengths” of a and b having the same parity (see the text for the definition of the “length” of a natural number). Also we will show that for any n∈N, n>2, n≠5, 10, there exist a, b∈N* such that n=a+b, the “lengths” of a and b having different parities. We will prove also that for any prime p≡7(mod 8) there exist a, b∈N* such that p=a²+b, the “length” of b being an even number.     

An all-substrings common subsequence algorithm

Given two strings A and B of lengths n_a and n_b, n_a?n_b, respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B^′ of B, the length of the longest string that is a subsequence of both A and B^′. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm to prepare the basic data structure for ALCS queries that takes O(n_an_b) time and O(n_a+n_b) space. After this preparation, it is possible to build a matrix of size that allows any LCS length to be retrieved in constant time. Some trade-offs between the space required and the querying time are discussed. To our knowledge, this is the first algorithm in the literature for the ALCS problem.     

Asymptotic behavior of solutions of the functional differential equation x′(t) = Ax(λt) + Bx(t), λ>0

The author discusses the asymptotic behavior of the solutions of the functional differential equation x′(t) = Ax(λt) + Bx(t), λ>0 (1) where x(t) is an n-dimensional column vector and A, B are n × n matrices with complex constant entries. He obtains the following results for the case 0 < λ < 1: (i) If B is diagonalizable with eigenvalues b_i such that Re b_i < 0 for all i, then there is a constant α such that every solution of (1) is O(t^α) as t → ∞. (ii) If B is diagonalizable with eigenvalues b_i such that 0 < Re b₁ ? Re b₂ ? ··· ? Re b_n and λ times Re b_n < Re b₁, then every solution of (1) is O(e^bn^t) as t → ∞. For the case λ>1, he has the following results: (i) If B is diagonalizable with eigenvalues b_i such that Re b_i>0 for all i, then there is a constant α such that no solution x(t) of (1), except the identically zero solution, is 0(t^α) as t → ∞. (ii) If B is diagonalizable with eigenvalues b_i such that Re b₁ ? Re b₂ ? ··· ? Re b_n < 0 and λ Re b_n < Re b₁, then no solution x(t) of (1), except the identically zero solution, is 0(e^b1^t) as t → ∞.     

Extensions and the Induced Characters of Cyclic p-Groups

For a prime p, we denote by B_n the cyclic group of order pⁿ. Let φ be a faithful irreducible character of B_n, where p is an odd prime. We study the p-group G containing B_n such that the induced character φ^G is also irreducible. The purpose of this article is to determine the subgroup N_G(N_G(B_n)) of G under the hypothesis [N_G(B_n):B_n]⁴ ≦ pⁿ.     

Randomized isomorphic Dvoretzky theoremVersion aléatoire isomorphique du théorème de Dvoretzky

Let K be a symmetric convex body in $\text{R}{}^{\mathrm{N}}$ for which B₂^N is the ellipsoid of minimal volume. We provide estimates for the geometric distance of a ‘typical’ rank n projection of K to B₂ⁿ, for 1?n<N. Known examples show that the resulting estimates are optimal (up to numerical constants) even for the Banach–Mazur distance. To cite this article: A. Litvak et al., C. R. Acad. Sci. Paris, Ser. I 335 (2002) 345–350.     

Vertical versus horizontal Poincaré inequalities on the Heisenberg group

Let ? = 〈a, b|a[a, b] = [a, b]a ∧ b[a, b] = [a, b]b〉 be the discrete Heisenberg group, equipped with the left-invariant word metric d _W (·, ·) associated to the generating set {a, b, a ^?1, b ^?1}. Letting B _n = {x ∈ ?: d _W (x, e _?) ? n} denote the corresponding closed ball of radius n ∈ ?, and writing c = [a, b] = aba ^?1 b ^?1, we prove that if (X, ‖ · ‖X) is a Banach space whose modulus of uniform convexity has power type q ∈ [2,∞), then there exists K ∈ (0, ∞) such that every f: ? → X satisfies $$\sum\limits_{k = 1}^{{n^2}} {\sum\limits_{x \in {B_n}} {\frac{{\left\| {f(x{c^k}) - f(x)} \right\|_X^q}}{{{k^{1 + q/2}}}}} } \leqslant K\sum\limits_{x \in {B_{21n}}} {(\left\| {f(xa) - f(x)} \right\|_X^q + \left\| {f(xb) - f(x)} \right\|_X^q)} $$ . It follows that for every n ∈ ? the bi-Lipschitz distortion of every f: B _n → X is at least a constant multiple of (log n)^1/q , an asymptotically optimal estimate as n → ∞.     

Harmonic analysis of fractal measures

We consider affine systems inR ⁿ constructed from a given integral invertible and expansive matrixR, and a finite setB of translates,σ _bx:=R^–1x+b; the corresponding measure μ onR ⁿ is a probability measure fixed by the self-similarity $\mu = \left| B \right|^{ - 1} \sum\nolimits_{b \in B} {\mu o\sigma _b^{ - 1} } $ . There are twoa priori candidates for an associated orthogonal harmonic analysis: (i) the existence of some subset Λ inR ⁿ such that the exponentials {e^iλ·x}Λ form anorthogonal basis forL ²(μ); and (ii) the existence of a certaindual pair of representations of theC ^*-algebraO _N wheren is the cardinality of the setB. (For eachN, theC ^*-algebraO _N is known to be simple; it is also called the Cuntz algebra.) We show that, in the “typical” fractal case, the naive version (i) must be rejected; typically the orthogonal exponentials inL ²(μ) fail to span a dense subspace. Instead we show that theC ^*-algebraic version of an orthogonal harmonic analysis, namely (ii), is a natural substitute. It turns out that this version is still based on exponentialse ^iλ·x, but in a more indirect way. (See details in Section 5 below.) Our main result concerns the intrinsic geometric features of affine systems, based onR andB, such that μ has theC ^*-algebra property (ii). Specifically, we show that μ has an orthogonal harmonic analysis (in the sense (ii)) if the system (R, B) satisfies some specific symmetry conditions (which are geometric in nature). Our conditions for (ii) are stated in terms of two pieces of data: (a) aunitary generalized Hadamard matrix, and (b) a certainsystem of lattices which must exist and, at the same time, be compatible with the Hadamard matrix. A partial converse to this result is also given. Several examples are calculated, and a new maximality condition for exponentials is identified.     

A generalization of N-matrices

Ky Fan defines an N-matrix to be a matrix of the form A = tI ? B, B ? 0, λ < t < ?(B), where ?(B) is the spectral radius of B and λ is the maximum of the spectral radii of all principal submatrices of B of order n ? 1. In this paper, we define the closure (N₀-matrices) of N-matrices by letting λ ? t. It is shown that if A ∈ Z and A^-1 < 0, then A ∈ N. Certain inequalities of N-matrices are shown to hold for N₀-matrices, and a method for constructing an N-matrix from an M-matrix is given.     

Brownian Gibbs property for Airy line ensembles

Consider a collection of N Brownian bridges $B_{i}:[-N,N] \to \mathbb{R} $ , B _i (?N)=B _i (N)=0, 1≤i≤N, conditioned not to intersect. The edge-scaling limit of this system is obtained by taking a weak limit as N→∞ of the collection of curves scaled so that the point (0,2^1/2 N) is fixed and space is squeezed, horizontally by a factor of N ^2/3 and vertically by N ^1/3. If a parabola is added to each of the curves of this scaling limit, an x-translation invariant process sometimes called the multi-line Airy process is obtained. We prove the existence of a version of this process (which we call the Airy line ensemble) in which the curves are almost surely everywhere continuous and non-intersecting. This process naturally arises in the study of growth processes and random matrix ensembles, as do related processes with “wanderers” and “outliers”. We formulate our results to treat these relatives as well. Note that the law of the finite collection of Brownian bridges above has the property—called the Brownian Gibbs property—of being invariant under the following action. Select an index 1≤k≤N and erase B _k on a fixed time interval (a,b)?(?N,N); then replace this erased curve with a new curve on (a,b) according to the law of a Brownian bridge between the two existing endpoints (a,B _k (a)) and (b,B _k (b)), conditioned to intersect neither the curve above nor the one below. We show that this property is preserved under the edge-scaling limit and thus establish that the Airy line ensemble has the Brownian Gibbs property. An immediate consequence of the Brownian Gibbs property is a confirmation of the prediction of M. Prähofer and H. Spohn that each line of the Airy line ensemble is locally absolutely continuous with respect to Brownian motion. We also obtain a proof of the long-standing conjecture of K. Johansson that the top line of the Airy line ensemble minus a parabola attains its maximum at a unique point. This establishes the asymptotic law of the transversal fluctuation of last passage percolation with geometric weights. Our probabilistic approach complements the perspective of exactly solvable systems which is often taken in studying the multi-line Airy process, and readily yields several other interesting properties of this process.     

The primitive Boolean matrices with the second largest scrambling index by Boolean rank

The scrambling index of an n × n primitive Boolean matrix A is the smallest positive integer k such that A ^k (A ^T) ^k = J, where A ^T denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M = AB for some m × b Boolean matrix A and b×n Boolean matrix B. In 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M), and they also characterized all primitive matrices that achieve the upper bound. In this paper, we characterize primitive Boolean matrices that achieve the second largest scrambling index in terms of their Boolean rank.     

Schwarzian derivative in Kähler manifolds (II)

Two injectivity theorems are proved which are for objective manifoldN = ??ⁿ andN =B ⁿ (unit ball), both equipped with canonical metric. Thus, the injectivity theorems are established in three cases of objective manifolds, i.e. with different holomorphic sectional curvatures - 1, 0 and 1 respectively.     

Multiplicative representations of integers

Lehh ≧ 2, and let ?=(B ₁, …,B _h ), whereB ₁ ? N={1, 2, 3, …} fori=1, …,h. Denote by g_?(n) the number of representations ofn in the formn=b ₁ …b _h , whereb _i ∈B _i . If v (n) > 0 for alln >n ₀, then ? is anasymptotic multiplicative system of order h. The setB is anasymptotic multiplicative basis of order h ifn=b ₁ …b _n is solvable withb _i ∈B for alln >n ₀. Denote byg(n) the number of such representations ofn. LetM(h) be the set of all pairs (s, t), wheres=lim g_? (n) andt=lim g_? (n) for some multiplicative system ? of orderh. It is proved that {fx129-1} In particular, it follows thats ≧ 2 impliest=∞. A corollary is a theorem of Erdös that ifB is a multiplicative basis of orderh ≧ 2, then lim g_? g(n)=∞. Similar results are obtained for asymptotic union bases of finite subsets of N and for asymptotic least common multiple bases of integers.     

Segmental solutions of Boolean equations

Davio and Deschamps have shown that the solution set, K, of a consistent Boolean equation $\text{?(x}{}_1\text{, …, x}{}_{\mathrm{n}}\text{)=0}$ over a finite Boolean algebra B may be expressed as the union of a collection of subsets of Bⁿ, each of the form {(x₁, …, x_n) | a_i≤x_i≤b_i, a_i?B, b_i?B, i = 1, …, n}. We refer to such subsets of Bⁿ as segments and to the collection as a segmental cover of K. We show that $\text{?(x}{}_1\text{, …, x}{}_{\mathrm{n}}\text{) = 1}$ is consistent if and only if ? can be expressed by one of a class of sum-of-products expressions which we call segmental formulas. The object of this paper is to relate segmental covers of K to segmental formulas for ?.     

On minimal two-spheres immersed in complex Grassmann manifolds with parallel second fundamental form

In this paper, we study some properties of the linearly full conformal minimal immersions φ : S ² → G(k, n) with second fundamental form B. At first we compute the Laplacian of square length ||B||² of B and the relations of Gaussian curvature K and normal curvature K ^N . Then we obtain a necessary and sufficient condition of the parallel second fundamental form, and prove that K must be constant if B is parallel. Moreover, if it is not totally geodesic, K ≤?||B||²/2, especially, K =?||B||²/2 when it is holomorphic. We also consider the pseudo-holomorphic curve in G(k, n) with parallel second fundamental form and compute its Gaussian curvature and K?hler angle.     

Extension de quelques theoremes sur les densites de series d'elements de n a des series de sous-ensembles finis de n

For a sequence A = {A_k} of finite subsets of N we introduce: $\text{δ(A) =}\text{inf}{}_{\mathrm{m?n}}\text{A(m)}\text{2}{}^{\mathrm{n}}$, $\text{d(A) =}\text{lim inf}{}_{\mathrm{n\to \infty }}\text{A(n)}\text{2}{}^{\mathrm{n}}$, where A(m) is the number of subsets A_k ? {1, 2, …, m}.The collection of all subsets of {1, …, n} together with the operation $\text{a ∪ b, (a ∩ b), (a 1 b = a ∪ b ? a ∩ b)}$ constitutes a finite semi-group N^∪ (semi-group N^∩) (group $\text{N}{}^1$). For N^∪, N^∩ we prove analogues of the Erdös-Landau theorem: δ(A+B) ? δ(A)(1+(2λ)^?1(1?δ(A>))), where B is a base of N of the average order λ. We prove for $\text{N}{}^{\mathrm{\cup }}\text{, N}{}^{\mathrm{\cap }}\text{, N}{}^1$ analogues of Schnirelmann's theorem (that δ(A) + δ(B) > 1 implies δ(A + B) = 1) and the inequalities λ ? 2h, where h is the order of the base.We introduce the concept of divisibility of subsets: a|b if b is a continuation of a. We prove an analog of the Davenport-Erdös theorem: if d(A) > 0, then there exists an infinite sequence {A_kr}, where A_kr | A_kr+1 for r = 1, 2, …. In Section 6 we consider for $\text{N∪, N∩, N1}$ analogues of Rohrbach inequality: $\text{2n}\text{? g(n) ? 2}\text{n}$, where g(n) = min k over the subsets {a₁ < … < a_k} ? {0, 1, 2, …, n}, such that every m? {0, 1, 2, …, n} can be expressed as m = a_i + a_j.Pour une série A = {A_k} de sous-ensembles finis de N on introduit les densités: $\text{δ(A) =}\text{inf}{}_{\mathrm{m?n}}\text{A(m)}\text{2}{}^{\mathrm{m}}$, $\text{d(A) =}\text{lim inf}{}_{\mathrm{n\to \infty }}\text{A(n)}\text{2}{}^{\mathrm{n}}$ où A(m) est le nombre d'ensembles A_k ? {1, 2, …, m}. L'ensemble de toutes les parties de {1, 2, …, n} devient, pour les opérations $\text{a ∪ b, a ∩ b, a 1 b = a ∪ b ? a ∩ b}$, un semi-groupe fini N^∪, N^∩ ou un groupe N¹ respectivement. Pour N^∪, N^∩ on démontre l'analogue du théorème de Erdös-Landau: δ(A + B) ? δ(A)(1 + (2λ)^?1(1?δ(A))), où B est une base de N d'ordre moyen λ. On démontre pour $\text{N}{}^{\mathrm{\cup }}\text{, N}{}^{\mathrm{\cap }}\text{, N}{}^1$ l'analogue du théorème de Schnirelmann (si δ(A) + δ(B) > 1, alors δ(A + B) = 1) et les inégalités λ ? 2h, où h est l'ordre de base. On introduit le rapport de divisibilité des enembles: a|b, si b est une continuation de a. On démontre l'analogue du théorème de Davenport-Erdös: si d(A) > 0, alors il existe une sous-série infinie {A_kr}, où A_kr|A_kr+1, pour r = 1, 2, … . Dans le Paragraphe 6 on envisage pour N^∪, $\text{N}{}^{\mathrm{\cap }}\text{, N}{}^1$ les analogues de l'inégalité de Rohrbach: $\text{2n}\text{? g(n) ? 2}\text{n}$, où g(n) = min k pour les ensembles {a₁ < … < a_k} ? {0, 1, 2, …, n} tels que pour tout m? {0, 1, 2, …, n} on a m = a_i + a_j.     

A relation between spaces implied by their t-equivalence

We prove that if X and Y are t-equivalent spaces (that is, if Cp(X) and Cp(Y) are homeomorphic), then there are spaces Zn, locally closed subspaces Bn of Zn, and locally closed subspaces Yn of Y, n∈N⁺, such that each Zn admits a perfect finite-to-one mapping onto a closed subspace of Xn, Yn is an image under a perfect mapping of Bn, and Y=?{Yn:n∈N⁺}. It is deduced that some classes of spaces, which for metric spaces coincide with absolute Borelian classes, are preserved by t-equivalence. Also some limitations on the complexity of spaces t-equivalent to “nice” spaces are obtained.     

On finite x-decomposable groups for X = {1, 2, 4}

A normal subgroup N of a finite group G is called an n-decomposable subgroup if N is a union of n distinct conjugacy classes of G. Each finite nonabelian nonperfect group is proved to be isomorphic to Q ₁₂, or Z ₂ × A ₄, or G = ??a, b, c | a ¹¹ = b ⁵ = c ² = 1, b ^?1 ab = a ⁴, c ^?1 ac = a ^?1, c ^?1 bc = b ^?1?? if every nontrivial normal subgroup is 2- or 4-decomposable.     

On subword decomposition and balanced polynomials

Let H(x) be a monic polynomial over a finite field F=GF(q). Denote by Na(n) the number of coefficients in Hn which are equal to an element a∈F, and by G the set of elements a∈F^× such that Na(n)>0 for some n. We study the relationship between the numbers (Na(n))_a∈G and the patterns in the base q representation of n. This enables us to prove that for “most” n's we have Na(n)≈Nb(n), a,b∈G. Considering the case H=x+1, we provide new results on Pascal's triangle modulo a prime. We also provide analogous results for the triangle of Stirling numbers of the first kind.