Monotonic Solutions of a Functional Equation Arising from Simultaneous Utility Representations

The functional equation ?(h(x)) ? ?(h(y)) + ?(y) = ?(h(x ? y) + y) was solved by Aczél, Luce and Marley on the assumption that the functions are different iable. They posed the question of its strictly monotonic continuous solutions. The problem is solved using a uniqueness theorem. The continuity assumption on the functions is removed and the equation is also solved on a restricted domain.     

Ramanujan — Fourier series and a theorem of Ingham

Given two arithmetical functions f, g, we derive, under suitable conditions, asymptotic formulas for the convolution sums ∑ _n≤N f (n) _g (n + h) for a fixed number h. To this end, we develop the theory of Ramanujan expansions for arithmetical functions. Our results give new proofs of some old results of Ingham proved by him in 1927 using different techniques.     

The combinatorial structure of (m,n)-convex sets

LetS be a closed subset of a Hausdorff linear topological space,S having no isolated points, and letc _s (m) denote the largest integern for whichS is (m,n)-convex. Ifc _s (k)=0 andc _s (k+1)=1, then $$ c_s \left( m \right) = \sum\limits_{i = 1}^k {\left( {\begin{array}{*{20}c} {\left[ {\frac{{m + k - i}} {k}} \right]} \\ 2 \\ \end{array} } \right)} $$ . Moreover, ifT is a minimalm subset ofS, the combinatorial structure ofT is revealed.     

New solitary-wave special solutions with compact support for the nonlinear dispersive K(m,n) equations

The genuinely nonlinear dispersive K(m,n) equation, u_t+(u^m)_x+(uⁿ)_xxx=0, which exhibits compactons: solitons with compact support, is investigated. New solitary-wave solutions with compact support are developed. The specific cases, K(2,2) and K(3,3), are used to illustrate the pertinent features of the proposed scheme. An entirely new general formula for the solution of the K(m,n) equation is established, and the existing general formula is modified as well.     

Intersection properties of boxes in R d

A family of sets is calledn-pierceable if there exists a set ofn points such that each member of the family contains at least one of the points. Helly’s theorem on intersections of convex sets concerns 1-pierceable families. Here the following Helly-type problem is investigated: Ifd andn are positive integers, what is the leasth =h(d, n) such that a family of boxes (with parallel edges) ind-space isn-pierceable if each of itsh-membered subfamilies isn-pierceable? The somewhat unexpected solution is: (i)h(d, 2) equals3d for oddd and 3d?1 for evend; (ii)h(2, 3)=16; and (iii)h(d, n) is infinite for all (d, n) withd≧2 andn≧3 except for (d, n)=(2, 3).     

Permutation functions and (n,m)-commutativity of semigroups

By [4], a semigroupS is called an (n, m)-commutative semigroup (n, m ∈ ?⁺, the set of all positive integers) if $$x_1 x_2 \cdot \cdot \cdot x_n y_1 y_2 \cdot \cdot \cdot y_m = y_1 y_2 \cdot \cdot \cdot y_m x_1 x_2 \cdot \cdot \cdot x_n $$ holds for allx ₁,...,x _n ,y ₁,...,y _m ∈S It is evident that ifS is an (n, m)-commutative semigroup then it is (n′,m′)-commutative for alln′≥n andm′≥m. In this paper, for an arbitrary semigroupS, we determine all pairs (n, m) of positive integersn andm for which the semigroupS is (n, m)-commutative. In our investigation a special type of function mapping ?⁺ into itself plays an important role. These functions which are defined and discussed here will be called permutation functions.     

Stability of multi-compacton solutions and Backlund transformation in K(m,n,1)

We introduce a fifth-order K(m,n,1) equation with nonlinear dispersion to obtain multi-compacton solutions by Adomian decomposition method. Using the homogeneous balance (HB) method, we derive a Backlund transformation of a special equation K(2,2,1) to determine some solitary solutions of the equation. To study the stability of multi-compacton solutions in K(m,n,1) and to obtain some conservation laws, we present a similar fifth-order equation derived from Lagrangian. We finally show the linear stability of all obtained multi-compacton solutions.     

Fast and accurate tensor approximation of a multivariate convolution with linear scaling in dimension

In the present paper we present the tensor-product approximation of a multidimensional convolution transform discretized via a collocation-projection scheme on uniform or composite refined grids. Examples of convolving kernels are provided by the classical Newton, Slater (exponential) and Yukawa potentials, 1/‖x‖, and with x∈R^d. For piecewise constant elements on the uniform grid of size n^d, we prove quadratic convergence O(h²) in the mesh parameter h=1/n, and then justify the Richardson extrapolation method on a sequence of grids that improves the order of approximation up to O(h³). A fast algorithm of complexity O(dR₁R₂nlogn) is described for tensor-product convolution on uniform/composite grids of size n^d, where R₁,R₂ are tensor ranks of convolving functions. We also present the tensor-product convolution scheme in the two-level Tucker canonical format and discuss the consequent rank reduction strategy. Finally, we give numerical illustrations confirming: (a) the approximation theory for convolution schemes of order O(h²) and O(h³); (b) linear-logarithmic scaling of 1D discrete convolution on composite grids; (c) linear-logarithmic scaling in n of our tensor-product convolution method on an n×n×n grid in the range n≤16384.     

Gibbs rapidly samples colorings of G(n, d/n)

Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd?s–Rényi random graph G(n, d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n, d/n) is d(1?o(1)), it contains many nodes of degree of order (log n) / (log log n). The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n, d/n) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n ^{1+Ω(1 / log log} n) with high probability. High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including coloring. Almost all known sufficient conditions in terms of number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work we consider sampling q-colorings and show that for every d < ∞ there exists q(d) < ∞ such that for all q ≥ q(d) the mixing time of the Gibbs sampling on G(n, d/n) is polynomial in n with high probability. Our results are the first polynomial time mixing results proven for the coloring model on G(n, d/n) for d > 1 where the number of colors does not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). In previous work we have shown that similar results hold for the ferromagnetic Ising model. However, the proof for the Ising model crucially relied on monotonicity arguments and the “Weitz tree”, both of which have no counterparts in the coloring setting. Our proof presented here exploits in novel ways the local treelike structure of Erd?s–Rényi random graphs, block dynamics, spatial decay properties and coupling arguments. Our results give the first polynomial-time algorithm to approximately sample colorings on G(n, d/n) with a constant number of colors. They extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which there exists an α > 0 such that every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub-graph is the union of a tree and at most O(1) edges and where each simple path Γ of length O(log n) satisfies ${\sum_{u \in \Gamma}\sum_{v \neq u}\alpha^{d(u,v)} = O({\rm log} n)}$ . The results also generalize to the hard-core model at low fugacity and to general models of soft constraints at high temperatures.     

Existence, uniqueness and stability ofC m solutions of iterative functional equations

In this paper we discuss a relatively general kind of iterative functional equation G(x,f(x), ...,f ⁿ (x)) = 0 (for allx ∈J), whereJ is a connected closed subset of the real number axis ?,G∈C ^m (J ⁿ⁺¹, ?) andn ≥ 2. Using the method of approximating fixed points by small shift of maps, choosing suitable metrics on functional spaces and finding a relation between uniqueness and stability of fixed points of maps of general spaces, we prove the existence, uniqueness and stability ofCm solutions of the above equation for any integer m ≥ 0 under relatively weak conditions, and generalize related results in reference in different aspects.     

Generalized moments of additive functions

Elliott's generalization of the Turán-Kubilius inequality is further generalized by establishing an upper bound for the sum Σ_n≤xF(∣f(n) ? A∣), where f is a complex-valued additive arithmetical function, A an arbitrary number and F an arbitrary nonnegative-valued increasing function. A connected problem for group-valued functions is also considered.     

The least degree of identities in the subspace M 1 (m,k) (F) of the matrix superalgebra M (m,k)(F)

We determine the least degree of identities in the subspace M ₁ ^(m,k) (F) of the matrix superalgebra M ^(m,k)(F) over a field F for arbitrary m and k. For the subspace M ₁ ^(m,k) (F) (k > 1) we obtain concrete minimal identities and generalize some results by Chang and Domokos.     

The algebraic structure of the set of solutions to the Thue equation

Let Fn be a binary form with integral coefficients of degree n?2, let d denote the greatest common divisor of all non-zero coefficients of Fn, and let h?2 be an integer. We prove that if d=1 then the Thue equation (T) Fn(x,y)=h has relatively few solutions: if A is a subset of the set T(Fn,h) of all solutions to (T), with r:=card(A)?n+1, then

(#)

h divides the numberΔ(A):=_∏1?k<l?rδ(ξk,ξl),

where ξk=〈xk,yk〉∈A, 1?k?r, and δ(ξk,ξl)=xkyl−xlyk. As a corollary we obtain that if h is a prime number then, under weak assumptions on Fn, there is a partition of T(Fn,h) into at most n subsets maximal with respect to condition (#).     

Minimal quadratic residue cyclic codes of lengthp n(p odd prime)

The explicit expressions for the 2n + 1 primitive idempotents in $R_{p^ - } = F[x]/< x^{p^ - } - 1 > $ , whereF is the field of prime power orderq and the multiplicative order ofq modulop ⁿ is ?(p ⁿ)/2 (n ≥ 1 andp is an odd prime), are obtained. An algorithm for computing the generating polynomials of the minimal QR cyclic codes of lengthp ⁿ, generated by these primitive idempotents, is given and hence some bounds on the minimum distance of some QR codes of prime length overGF(q)(q = 2, 3, ...) are obtained.     

Basis of graded identities of the superalgebra M 1,2(F)

Denote by Mat _k,l (F) the algebraM _n (F) of matrices of order n = k + l with the grading (Mat _k,l ⁰ (F),Mat _k,l ¹ (F)), where Mat _k,l ⁰ (F) admits the basis $$ \{ e_{ij} ,i \leqslant k,j \leqslant k\} \cup \{ e_{ij} ,i > k,j > k\} $$ and Mat _k,l ¹ (F) admits the basis $$ \{ e_{ij} ,i \leqslant k,j > k\} \cup \{ e_{ij} ,i > k,j \geqslant k\} . $$ . Denote byM _k,l (F) the Grassmann envelope of the superalgebra Mat _k,l (F). In the paper, bases of the graded identities of the superalgebras Mat_1,2(F) and M _1,2(F) are described.     

C (n)-cardinals

For each natural number n, let C ⁽ⁿ⁾ be the closed and unbounded proper class of ordinals α such that V _α is a Σ _n elementary substructure of V. We say that κ is a C ⁽ⁿ⁾ -cardinal if it is the critical point of an elementary embedding j : V → M, M transitive, with j(κ) in C ⁽ⁿ⁾. By analyzing the notion of C ⁽ⁿ⁾-cardinal at various levels of the usual hierarchy of large cardinal principles we show that, starting at the level of superstrong cardinals and up to the level of rank-into-rank embeddings, C ⁽ⁿ⁾-cardinals form a much finer hierarchy. The naturalness of the notion of C ⁽ⁿ⁾-cardinal is exemplified by showing that the existence of C ⁽ⁿ⁾-extendible cardinals is equivalent to simple reflection principles for classes of structures, which generalize the notions of supercompact and extendible cardinals. Moreover, building on results of Bagaria et?al. (2010), we give new characterizations of Vopeňka’s Principle in terms of C ⁽ⁿ⁾-extendible cardinals.     

Zur Bestimmung vonE n [x n+2m ]

Remark on the estimation ofE _n [x ^n+2m ]. Let be $$E_n [f]: = \mathop {\inf }\limits_{p \in P_n } \mathop {\sup }\limits_{x \in [ - 1, 1]} |f(x) - p(x)|$$ (P _n : set of all polynomials of degreen). Riess-Johnson [4] proved (3) $$E_n [x^{n + 2m} ] = \frac{{n^{m - 1} }}{{2^{n + 2m - 1} (m - 1)!}}[1 + O(n^{ - 1} )],n even.$$ This degree of approximation is realized by expansion in Chebyshev polynomials and by interpolation at Chebyshev nodes. The purpose of this paper is to give a more precise estimation by constructing the polynomial of best approximation on a finite set. This construction is easily done and one obtains the result, that the termO(n ^?1) in (3) may be replaced by 1/2(m ? 1) (3m + 2)n ^?1 + O(n ^?2).     

New exact solitary-wave special solutions for the nonlinear dispersive K(m, n) equations

In this paper, we study the nonlinear dispersive K(m, n) equations: u_t + (u^m)_x − (uⁿ)_xxx = 0 which exhibit solutions with solitary patterns. New exact solitary solutions are found. The two special cases, K(2, 2) and K(3, 3), are chosen to illustrate the concrete features of the decomposition method in K(m, n) equations. The nonlinear equations K(m, n) are studied for two different cases, namely when m = n being odd and even integers. General formulas for the solutions of K(m, n) equations are established.     

Existence of triple solutions of discrete (n,p) boundary value problems

We consider the following boundary value problem: −Δⁿy = F(k,y, Δy,…,Δⁿ⁻¹y), k ϵ Z[n − 1, N], Δⁱy(0) = 0, 0 ≤ i ≤ n − 2, Δ^py(N + n - p) = 0, where n ≥ 2 and p is a fixed integer satisfying 0 ≤ p ≤ n − 1. Using a fixed-point theorem for operators on a cone, we shall yield the existence of at least three positive solutions.     

On the existence of (l,m,n)-spreads

We call a family ofm-flats of Pⁿ (K) an (l, m, n)-spread overK if it is a partition of the family of alll-flats. We prove two non-existence results for (l, m, n)-spreads in the case:K = GF(q) andl > 0.Alla memoria del Professor Giuseppe TalliniThis research was supported in part by M.U.R.S.T.