Combinatorial constructions for optimal 2-D optical orthogonal codes with AM-OPPTS property

We develop a new one-to-one correspondence between a two-dimensional (m × n, k, ρ) optical orthogonal code (2-D (m × n, k, ρ)-OOC) with AM-OPPTS (at most one-pulse per time slot) property and a certain combinatorial subject, called an n-cyclic holey packing of type m ⁿ . By this link, an upper bound on the size of a 2-D (m × n, k, ρ)-OOC with AM-OPPTS property is derived. Afterwards, we employ combinatorial methods to construct infinitely many 2-D (m × n, k, 1)-OOCs with AM-OPPTS property, whose existence was previously unknown. All these constructions meet the upper bounds with equality and are thus optimal.     

Convex solution of a permutation problem

In this paper, we show that a problem of finding a permuted version of k vectors from R^N such that they belong to a prescribed rank r subset, can be solved by convex optimization. We prove that under certain generic conditions, the wanted permutation matrix is unique in the convex set of doubly-stochastic matrices. In particular, this implies a solution of the classical correspondence problem of finding a permutation that transforms one collection of points in R^k into the another one. Solutions to these problems have a wide set of applications in Engineering and Computer Science.     

On multiple sum and product sets of finite sets of integers

Let $\text{A?}\text{Z}$ be a finite set of integers of cardinality |A|=N?2. Given a positive integer k, denote kA (resp. A^(k)) the set of all sums (resp. products) of k elements of A. We prove that for all b>1, there exists k=k(b) such that max(|kA|,|A^(k)|)>N^b. This answers affirmably questions raised in Erd?s and Szemerédi (Stud. Pure Math., 1983, pp. 213–218), Elekes et al. (J. Number Theory 83 (2) (2002) 194–201) and recently, by S. Konjagin (private communication). The method is based on harmonic analysis techniques in the spirit of Chang (Ann. Math. 157 (2003) 939–957) and combinatorics on graphs. To cite this article: J. Bourgain, M.-C. Chang, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

Free groups in a normal subgroup of the field of fractions of a skew polynomial ring

Let k(t) be the field of rational functions over the field k, let σ be a k-automorphism of K = k(t), let D = K(X;σ) be the ring of fractions of the skew polynomial ring K[X;σ], and let D^? be the multiplicative group of D. We show that if N is a noncentral normal subgroup of D^?, then N contains a free subgroup. We also prove that when k is algebraically closed and σ has infinite order, there exists a specialization from D to a quaternion algebra. This allows us to explicitly present free subgroups in D^?.     

Positivity of Riesz functionals and solutions of quadratic and quartic moment problems

We employ positivity of Riesz functionals to establish representing measures (or approximate representing measures) for truncated multivariate moment sequences. For a truncated moment sequence y, we show that y lies in the closure of truncated moment sequences admitting representing measures supported in a prescribed closed set K⊆Rn if and only if the associated Riesz functional Ly is K-positive. For a determining set K, we prove that if Ly is strictly K-positive, then y admits a representing measure supported in K. As a consequence, we are able to solve the truncated K-moment problem of degree k in the cases: (i) (n,k)=(2,4) and K=R²; (ii) n?1, k=2, and K is defined by one quadratic equality or inequality. In particular, these results solve the truncated moment problem in the remaining open cases of Hilbert's theorem on sums of squares.     

On sets of type (q + 1, n)2 in finite three-dimensional projective spaces

It is proved that a k–set of type (q + 1, n)₂ in PG(3, q) either is a plane or it has size k ≥ (q + 1)² and a characterization of some sets of size (q + 1)² is given.     

Improved sparse fourier approximation results: faster implementations and stronger guarantees

We study the problem of quickly estimating the best k-term Fourier representation for a given periodic function f: [0, 2π] → ?. Solving this problem requires the identification of k of the largest magnitude Fourier series coefficients of f in worst case k ² · log ^O(1) N time. Randomized sublinear-time Monte Carlo algorithms, which have a small probability of failing to output accurate answers for each input signal, have been developed for solving this problem (Gilbert et al. 2002, 2005). These methods were implemented as the Ann Arbor Fast Fourier Transform (AAFFT) and empirically evaluated in Iwen et al. (Commun Math Sci 5(4):981–998, 2007). In this paper we present a new implementation, called the Gopher Fast Fourier Transform (GFFT), of more recently developed sparse Fourier transform techniques (Iwen, Found Comput Math 10(3):303–338, 2010, Appl Comput Harmon Anal, 2012). Experiments indicate that GFFT is faster than AAFFT. In addition to our empirical evaluation, we also consider the existence of sublinear-time Fourier approximation methods with deterministic approximation guarantees for functions whose sequences of Fourier series coefficents are compressible. In particular, we prove the existence of sublinear-time Las Vegas Fourier Transforms which improve on the recent deterministic Fourier approximation results of Iwen (Found Comput Math 10(3):303–338, 2010, Appl Comput Harmon Anal, 2012) for Fourier compressible functions by guaranteeing accurate answers while using an asymptotically near-optimal number of function evaluations.     

Structural and geometric characteristics of sets of convergence and divergence of multiple Fourier series with J k -lacunary sequence of rectangular partial sums

We study multiple trigonometric Fourier series of functions f in the classes $L_p \left( {\mathbb{T}^N } \right)$ , p > 1, which equal zero on some set $\mathfrak{A}, \mathfrak{A} \subset \mathbb{T}^N , \mu \mathfrak{A} > 0$ (µ is the Lebesgue measure), $\mathbb{T}^N = \left[ { - \pi ,\pi } \right]^N$ , N ≥ 3. We consider the case when rectangular partial sums of the indicated Fourier series S _n (x; f) have index n = (n ₁, ..., n _N ) ∈ ? ^N , in which k (k ≥ 1) components on the places {j ₁, ..., j _k } = J _k ? {1, ..., N} are elements of (single) lacunary sequences (i.e., we consider multiple Fourier series with J _k -lacunary sequence of partial sums). A correlation is found of the number k and location (the “sample” J _k ) of lacunary sequences in the index n with the structural and geometric characteristics of the set $\mathfrak{A}$ , which determines possibility of convergence almost everywhere of the considered series on some subset of positive measure $\mathfrak{A}_1$ of the set $\mathfrak{A}$ .     

Relative Brauer Groups of Function Fields of Curves of Genus One

Abstract

Let Kbe an algebraic function field in one variable over a constant field k. In this paper, we investigate the relative Brauer groups Br(K/k) of Kover kin various cases. When kis a global field, we focus on function fields K = k(C) of genus 1 where Cis the curve of the form y ² = at ⁴ + bwith a, b ∈ k ? {0}, and we describe the Brauer classes in Br(K/k). More precisely, we show that each algebra in Br(K/k) is a quaternion algebra which can be obtained by taking one of a finite number of the x-coordinates of k-rational points on the Jacobian of the curve C. In particular, for the field ? of rational numbers, we determine Br(K/?) precisely in numerous cases and give examples.     

On exact recovery of sparse vectors from linear measurements

Let 1 ≤ k ≤ n < N. We say that a vector x ∈ ? ^N is k-sparse if it has at most k nonzero coordinates. Let Φ be an n × N matrix. We consider the problem of recovery of a k-sparse vector x ∈ ? ^N from the vector y = Φx ∈ ? ⁿ . We obtain almost-sharp necessary conditions for k, n, N for this problem to be reduced to that of minimization of the ?₁-norm of vectors z satisfying the condition y = Φz.     

A generalization of Sen–Brinon’s theory

Let K be a complete discrete valuation field of mixed characteristic and k be its residue field of prime characteristic p > 0. We assume that [k : k ^p ] = p ^h < ∞. Let G _K be the absolute Galois group of K and ${\mathcal{R}}$ be a Banach algebra over ${\mathbb{C}_p:=\widehat{\overline{K}}}$ with a continuous action of G _K . When k is perfect (i.e. h = 0), Sen studied the Galois cohomology ${{\rm H}^1(G_K, \mathcal{R}^\ast)}$ and Sen’s operator associated to each class (Sen Ann Math 127:647–661, 1988). In this paper we generalize Sen’s theory to the case h ≥ 0 by using Brinon’s theory (Brinon Math Ann 327:793–813, 2003). We also give another formulation of Brinon’s theorem (à la Colmez).     

Packing Triangles in K 4-Free Graphs

Paul Erd?s conjectured that every K ₄-free graph of order n and size ${k + \lfloor n^2/4\rfloor}$ contains at least k edge disjoint triangles. In this note, we prove that such a graph contains at least 32k/35 + o(n ²) edge disjoint triangles and prove his conjecture for k ≥  0.077n ².     

On Polygons Excluding Point Sets

By a polygonization of a finite point set S in the plane we understand a simple polygon having S as the set of its vertices. Let B and R be sets of blue and red points, respectively, in the plane such that ${B\cup R}$ is in general position, and the convex hull of B contains k interior blue points and l interior red points. Hurtado et al. found sufficient conditions for the existence of a blue polygonization that encloses all red points. We consider the dual question of the existence of a blue polygonization that excludes all red points R. We show that there is a minimal number K = K(l), which is bounded from above by a polynomial in l, such that one can always find a blue polygonization excluding all red points, whenever k ≥ K. Some other related problems are also considered.     

Counting sets with small sumset and applications

We study the number of k-element sets A? {1,...,N} with |A+A| ≤ K|A| for some (fixed) K > 0. Improving results of the first author and of Alon, Balogh, Samotij and the second author, we determine this number up to a factor of 2 ^{o ( k )} N ^{o (1)} for most N and k. As a consequence of this and a further new result concerning the number of sets A??/N? with |A+A| ≤ c|A|², we deduce that the random Cayley graph on ?/N? with edge density ½ has no clique or independent set of size greater than (2+o(1)) log₂ N, asymptotically the same as for the Erd?s-Rényi random graph. This improves a result of the first author from 2003 in which a bound of 160log₂ N was obtained. As a second application, we show that if the elements of A ? ? are chosen at random, each with probability 1/2, then the probability that A+A misses exactly k elements of ? is equal to (2+O(1))^?k/2 as k → ∞.     

Convex polarities over ordered fields

We use tools and methods from real algebraic geometry (spaces of ultrafilters, elimination of quantifiers) to formulate a theory of convexity in K^N over an arbitrary ordered field. By defining certain ideal points (which can be viewed as generalizations of recession cones) we obtain a generalized notion of polar set. These satisfy a form of polar duality that applies to general convex sets and does not reduce to classical duality if K is the field of real numbers. As an application we give a partial classification of total orderings of Artinian local rings and two applications to ordinary convex geometry over the real numbers.     

Steady magnetohydrodynamic flow in a diverging channel with suction or blowing

An analysis is made of steady two-dimensional divergent flow of an electrically conducting incompressible viscous fluid in a channel formed by two non-parallel walls, the flow being caused by a source of fluid volume at the intersection of the walls. The fluid is permeated by a magnetic field produced by an electric current along the line of intersection of the channel walls. The walls are porous and subjected to either suction (k > 0) or blowing (k < 0) of equal magnitude on both the walls. It is found that when the Reynolds number for the flow is large and the magnetic Reynolds number is very small, boundary layers are formed on the channel walls such that a sufficient condition for the existence of a unique boundary layer solution (without separation) in the case of suction is N > 2, N being the magnetic parameter. When k = 0, boundary layer exists without separation only when N > 2. Further, it is found that the necessary and sufficient condition for the existence of a unique solution for boundary layer flow (without separation) even in the presence of blowing (k < 0) is N > 2. For given value of k, velocity at a point increases with increase in N. It is also shown that when N > 2, blowing makes the boundary layer thinner. A similarity solution for steady temperature distribution in the divergent flow is also presented when the channel walls are held at variable temperature. It is found that for fixed value of wall suction, temperature at a point decreases with increase in N. It is further shown that when N > 2, steady distribution of temperature exists even in the case of blowing at the walls.     

Generalized vector-valued paranormed sequence space using modulus function

In this paper we introduce a generalized vector-valued paranormed sequence space N_p(E_k,Δ^m,f,s) using modulus function f, where p=(p_k) is a bounded sequence of positive real numbers such that inf_kp_k>0,(E_k,q_k) is a sequence of seminormed spaces with E_k+1⊆E_k for each k ∈ N and s?0. We have also studied sequence space N_p(E_k,Δ^m,f^r,s), where f^r=f°f°f°,…,f (r-times composition of f with itself) and r∈N={1,2,3,…}. Results regarding completeness, K-space, normality, inclusion relations etc. are derived. Further, a study of multiplier of the set N_p(E_k,f,s) is also made by choosing (E_k,‖·‖_k) as sequence of normed algebras.     

Flip Graphs of Bounded Degree Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n ²). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4.     

More DD difference sets

Dillon and Dobbertin proved that if L := GF(2 ^m ), gcd(k, m) = 1, d := 4 ^k ? 2 ^k + 1 and Δ _k (x) := (x + 1) ^d + x ^d + 1, then B _k := L\Δ _k (L) is a difference set in the cyclic multiplicative group L  ^×  of L. Used in the proof were the auxiliary functions $c_k^{\gamma}(x) := b_k(\gamma x^{2^k+1})$ , where γ is in L  ^×  and b _k is the characteristic function of B _k on L. When m is odd $c_k^{\gamma}$ is itself the characteristic function of a cyclic difference set which is equivalent to B _k . In this paper we point out that when m is even and γ is not a cube in L then $c_k^{\gamma}$ is the characteristic function of a difference set in the elementary abelian additive group of L; i.e. $c_k^{\gamma}$ is a bent function.     

Binary codes and partial permutation decoding sets from the odd graphs

For k ≥ 1, the odd graph denoted by O(k), is the graph with the vertex-set Ω^{k}, the set of all k-subsets of Ω = {1, 2, …, 2k +1}, and any two of its vertices u and v constitute an edge [u, v] if and only if u ∩ v = /0. In this paper the binary code generated by the adjacency matrix of O(k) is studied. The automorphism group of the code is determined, and by identifying a suitable information set, a 2-PD-set of the order of k ⁴ is determined. Lastly, the relationship between the dual code from O(k) and the code from its graph-theoretical complement $\overline {O(k)} $ , is investigated.