On sets of integers whose shifted products are powers

Let N be a positive integer and let A be a subset of {1,…,N} with the property that aa^′+1 is a pure power whenever a and a^′ are distinct elements of A. We prove that |A|, the cardinality of A, is not large. In particular, we show that |A|?(logN)^2/3(loglogN)^1/3.     

Symmetric Monge–Kantorovich problems and polar decompositions of vector fields

We address the problem of whether a bounded measurable vector field from a bounded domain Ω into \({\mathbb{R}^d}\) is N-cyclically monotone up to a measure preserving N-involution, where N is any integer larger than 2. Our approach involves the solution of a multidimensional symmetric Monge–Kantorovich problem, which we first study in the case of a general cost function on a product domain Ω ^N . The polar decomposition described above corresponds to a special cost function derived from the vector field in question (actually N ? 1 of them). The problem amounts to showing that the supremum in the corresponding Monge–Kantorovich problem when restricted to those probability measures on Ω ^N which are invariant under cyclic permutations and with a given first marginal μ, is attained on a probability measure that is supported on a graph of the form x → (x, Sx, S ² x,..., S ^N-1 x), where S is a μ-measure preserving transformation on Ω such that S ^N  = I a.e. The proof exploits a remarkable duality between such involutions and those Hamiltonians that are N-cyclically antisymmetric.     

On the enumeration of chains in regular chain-groups

Let N be a regular chain-group on E (see W. T. Tutte, Canad. J. Math.8 (1956), 13–28); for instance, N may be the group of integer flows or tensions of a directed graph with edge-set E). It is known that the number of proper Z_λ-chains of N (λ ∈ Z, λ ≥ 2) is given by a polynomial in λ, P(N, λ) (when N is the chain-group of integer tensions of the connected graph G, λP(N, λ) is the usual chromatic polynomial of G). We prove the formula: P(N, λ) = Σ_{[E′]∈O(N)⁺/～}Q(R_[E′](N), λ), where O(N)⁺ is the set of orientations of N with a proper positive chain, ～ is a simple equivalence relation on O(N)⁺ (sequence of reversals of positive primitive chains), and Q(R_[E′](N), λ) is the number of chains with values in [1, λ ? 1] in any reorientation of N associated to an element of [E′]. Moreover, each term Q(R_[E′](N), λ) is a polynomial in λ. As applications we obtain: P(N, 0) = (?1)^r(N)∥O(N)⁺/～∥; P(N, ?1) = (?1)^r(N)∥O(N)⁺∥ (a result first proved by Brylawski and Lucas); P(N, λ + 1) ≥ P(N, λ) for λ ≥ 2, λ ∈ Z. Our result can also be considered as a refinement of the following known fact: A regular chain-group N has a proper Z_λ-chain iff it has a proper chain in [?λ + 1, λ ? 1].     

Boundaries and complements of infinite- dimensional manifolds in the model space

Let M be a manifold modeled on a locally convex linear metric space E≌E^ω (or ≌E^ω_f and N a Z-submanifold of M. Then N is collared in M. In this paper, we study the following problem [1, 3]: Under what conditions can M be embedded in E so that N is the topological boundary of M in E? We gain a more mild sufficient condition than the previous papers [7, 8] and a necessary and sufficient condition in the case M has the homotopy type of Sⁿ (and each component of N is simply connected if n?2) and in the case N has the homotopy type of Sⁿ (n?2). Also we obtain a necessary and sufficient condition under which M can be embedded in E so that bd M = N and cl(E\M) has the homotopy type of Sⁿ (we assume that M and N are simply connected if n ? 2).     

Coupling of a multilevel fast multipole method and a microlocal discretization for the 3-D integral equations of electromagnetism

The aim of this work is to propose an accurate and efficient numerical approximation for high frequency diffraction of electromagnetic waves. In the context of the boundary integral equations presented in F. Collino and B. Després, to be published in J. Comput. Appl. Math., the strategy we propose combines the microlocal discretization (T. Abboud et al., in: Third International Conference on Mathematical Aspects of Wave Propagation Phenomena, SIAM, 1995, pp. 178–187) and the multilevel fast multipole method (J.M. Song, W.C. Chew, Microw. Opt. Tech. Lett. 10 (1) (1995) 14–19). This leads to a numerical method with a reduced complexity, of order O(N^4/3ln(N)+N_iterN^2/3), instead of the complexity O(N_iterN²) for a classical numerical iterative solution of integral equations. Computations on an academic geometry show that the new method improves the efficiency, for a solution with a good level of accuracy. To cite this article: A. Bachelot et al., C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Discrepancy of Arithmetic Progressions in Higher Dimensions

K. F. Roth (1964, Acta. Arith.9, 257-260) proved that the discrepancy of arithmetic progressions contained in [1, N]={1, 2, …, N} is at least cN^1/4, and later it was proved that this result is sharp. We consider the d-dimensional version of this problem. We give a lower estimate for the discrepancy of arithmetic progressions on [1, N]^d and prove that this result is nearly sharp. We use our results to give an upper estimate for the discrepancy of lines on an N×N lattice, and we also give an estimate for the discrepancy of a related random hypergraph.     

Type III1 equilibrium states of the Toeplitz algebra of the affine semigroup over the natural numbers

We complete the analysis of KMS-states of the Toeplitz algebra T(N?N^×) of the affine semigroup over the natural numbers, recently studied by Raeburn and the first author, by showing that for every inverse temperature β in the critical interval 1?β?2, the unique KMSβ-state is of type III₁. We prove this by reducing the type classification from T(N?N^×) to that of the symmetric part of the Bost-Connes system, with a shift in inverse temperature. To carry out this reduction we first obtain a parametrization of the Nica spectrum of N?N^× in terms of an adelic space. Combining a characterization of traces on crossed products due to the second author with an analysis of the action of N?N^× on the Nica spectrum, we can also recover all the KMS-states of T(N?N^×) originally computed by Raeburn and the first author. Our computation sheds light on why there is a free transitive circle action on the extremal KMSβ-states for β>2 that does not ostensibly come from an action of T on the C^?-algebra.     

Partially ordered knapsack and applications to scheduling

In the partially ordered knapsack problem (POK) we are given a set N of items and a partial order ?_P on N. Each item has a size and an associated weight. The objective is to pack a set N^′⊆N of maximum weight in a knapsack of bounded size. N^′ should be precedence-closed, i.e., be a valid prefix of ?_P. POK is a natural generalization, for which very little is known, of the classical Knapsack problem. In this paper we present both positive and negative results. We give an FPTAS for the important case of a two-dimensional partial order, a class of partial orders which is a substantial generalization of the series-parallel class, and we identify the first non-trivial special case for which a polynomial-time algorithm exists. Our results have implications for approximation algorithms for scheduling precedence-constrained jobs on a single machine to minimize the sum of weighted completion times, a problem closely related to POK.     

Divided powers in Chow rings and integral Fourier transforms

We prove that for any monoid scheme M over a field with proper multiplication maps M×M→M, we have a natural PD-structure on the ideal CH>0(M)⊂CH_∗(M) with regard to the Pontryagin ring structure. Further we investigate to what extent it is possible to define a Fourier transform on the motive with integral coefficients of the Jacobian of a curve. For a hyperelliptic curve of genus g with sufficiently many k-rational Weierstrass points, we construct such an integral Fourier transform with all the usual properties up to N²-torsion, where N=1+⌊log₂(3g)⌋. As a consequence we obtain, over , a PD-structure (for the intersection product) on N²⋅a, where a⊂CH(J) is the augmentation ideal. We show that a factor 2 in the properties of an integral Fourier transform cannot be eliminated even for elliptic curves over an algebraically closed field.     

Displacement ranks of matrices and linear equations

It takes of the order of N³ operations to solve a set of N linear equations in N unknowns or to invert the corresponding coefficient matrix. When the underlying physical problem has some time- or shift-invariance properties, the coefficient matrix is of Toeplitz (or difference or convolution) type and it is known that it can be inverted with O(N²) operations. However non-Toeplitz matrices often arise even in problems with some underlying time-invariance, e.g., as inverses or products or sums of products of possibly rectangular Toeplitz matrices. These non-Toeplitz matrices should be invertible with a complexity between O(N²) and O(N³). In this paper we provide some content for this feeling by introducing the concept of displacement ranks, which serve as a measure of how ‘close’ to Toeplitz a given matrix is.     

Bases and closures under infinite sums

Motivated by work of Diestel and Kühn on the cycle spaces of infinite graphs we study the ramifications of allowing infinite sums in a module R^M. We show that every generating set in this setup contains a basis if the ground set M is countable, but not necessarily otherwise. Given a family N⊆R^M, we determine when the infinite-sum span N of N is closed under infinite sums, i.e. when N=N. We prove that this is the case if R is a field or a finite ring and each element of M lies in the support of only finitely many elements of N. This is, in a sense, best possible. We finally relate closures under infinite sums to topological closures in the product space R^M.     

Hecke Eigenfunctions of Quantized Cat Maps Modulo Prime Powers

This paper continues the work done in Olofsson [Commun Math Phys 286(3):1051–1072, 2009] about the supremum norm of eigenfunctions of desymmetrized quantized cat maps. N will denote the inverse of Planck’s constant and we will see that the arithmetic properties of N play an important role. We prove the sharp estimate ||ψ||_∞ = O(N ^1/4) for all normalized eigenfunctions and all N outside of a small exceptional set. We are also able to calculate the value of the supremum norms for most of the so called newforms. For a given N = p ⁿ , with n > 2, the newforms can be divided in two parts (leaving out a small number of them in some cases), the first half all have supremum norm about ${2/\sqrt{1\pm 1/p}}This paper continues the work done in Olofsson [Commun Math Phys 286(3):1051–1072, 2009] about the supremum norm of eigenfunctions of desymmetrized quantized cat maps. N will denote the inverse of Planck’s constant and we will see that the arithmetic properties of N play an important role. We prove the sharp estimate ||ψ||_∞ = O(N ^1/4) for all normalized eigenfunctions and all N outside of a small exceptional set. We are also able to calculate the value of the supremum norms for most of the so called newforms. For a given N = p ⁿ , with n > 2, the newforms can be divided in two parts (leaving out a small number of them in some cases), the first half all have supremum norm about 2/?{1±1/p}{2/\sqrt{1\pm 1/p}} and the supremum norm of the newforms in the second half have at most three different values, all of the order N ^1/6. The only dependence of A is that the normalization factor is different if A has eigenvectors modulo p or not. We also calculate the joint value distribution of the absolute value of n different newforms.     

On inner automorphisms and certain central automorphisms of groups

Let G be a group, let M and N be two normal subgroups of G. We denote by Aut _N ^M (G), the set of all automorphisms of G which centralize G/M and N. In this paper we investigate the structure of a group G in which one of the Inn(G) = Aut _N ^M (G), Aut _N ^M (G) ≤ Inn(G) or Inn(G) ≤ Aut _N ^M (G) holds. We also discuss the problem: “what conditions on G is sufficient to ensure that G has a non-inner automorphism which centralizes G/M and N”.     

Hilbert cubes in progression-free sets and in the set of squares

We present a new method to give upper bounds on the dimension of Hilbert cubes in certain sets. As a special case we improve Hegyvári and Sárközy’s upper bound O((logN)^1/3) for the maximal dimension of a Hilbert cube in the set of squares in [1,N] to O((log logN)²).     

Necessary conditions for ɛ-uniform convergence of finite difference schemes for parabolic equations with moving boundary layers

A grid approximation of the boundary value problem for a singularly perturbed parabolic reaction-diffusion equation is considered in a domain with the boundaries moving along the axis x in the positive direction. For small values of the parameter ? (this is the coefficient of the higher order derivatives of the equation, ? ∈ (0, 1]), a moving boundary layer appears in a neighborhood of the left lateral boundary S ₁ ^L . In the case of stationary boundary layers, the classical finite difference schemes on piece-wise uniform grids condensing in the layers converge ?-uniformly at a rate of O(N ^?1lnN + N ₀), where N and N ₀ define the number of mesh points in x and t. For the problem examined in this paper, the classical finite difference schemes based on uniform grids converge only under the condition N ^?1 + N ₀ ^?1 ? ?. It turns out that, in the class of difference schemes on rectangular grids that are condensed in a neighborhood of S ₁ ^L with respect to x and t, the convergence under the condition N ^?1 + N ₀ ^?1 ≤ ?^1/2 cannot be achieved. Examination of widths that are similar to Kolmogorov’s widths makes it possible to establish necessary and sufficient conditions for the ?-uniform convergence of approximations of the solution to the boundary value problem. These conditions are used to design a scheme that converges ?-uniformly at a rate of O(N ^?1lnN + N ₀).     

Polynomial indexing of integer lattice-points I. General concepts and quadratic polynomials

Denoting the nonnegative integers by N and the signed integers by Z, we let S be a subset of Z^m for m = 1, 2,… and f be a mapping from S into N. We call f a storing function on S if it is injective into N, and a packing function on S if it is bijective onto N. Motivation for these concepts includes extendible storage schemes for multidimensional arrays, pairing functions from recursive function theory, and, historically earliest, diagonal enumeration of Cartesian products. Indeed, Cantor's 1878 denumerability proof for the product N² exhibits the equivalent packing functions $\text{f}{}_{\mathrm{<mtext>Cantor</mtext>}}\text{(x, y) = {}\text{either}\text{x}\text{or}\text{y} +}\text{(x + y)(x + y + 1)}\text{2}$ on the domain N², and a 1923 Fueter-Pólya result, in our terminology, shows f_Cantor the only quadratic packing function on N². This paper extends the preceding result. For any real-valued function f on S we define a density $\text{S ÷ f =}\text{lim}{}_{\mathrm{n\to \infty }}\text{(}\text{1}\text{n}\text{)\#{S ? f}{}^{\mathrm{?1}}\text{([?n, +n])}}$, and for any packing function f on S we observe the fact S ÷ f = 1. Using properties of this density, and invoking Davenport's lemma from geometric number theory, we find all polynomial storing functions with unit density on N, and exclude any polynomials with these properties on Z, then find all quadratic storing functions with unit density on N², and exclude any quadratics with these properties on Z × N, Z². The admissible quadratics on N² are all nonnegative translates of f_Cantor. An immediate sequel to this paper excludes some higher-degree polynomials on subsets of Z².     

Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n²) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n³) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.     

The $$\overline \partial $$-Neumann operator on Lipschitz q-pseudoconvex domains

On a bounded q-pseudoconvex domain Ω in ? ⁿ with a Lipschitz boundary, we prove that the \(\overline \partial \)-Neumann operator N satisfies a subelliptic (1/2)-estimate on Ω and N can be extended as a bounded operator from Sobolev (?1/2)-spaces to Sobolev (1/2)-spaces.