Variational Inequalities: an Elementary Approach

We will deal with the following problem: Let M be an n×n matrix with real entries. Under which conditions the family of inequalities: x∈? ⁿ ;x?0;M·x?0has non–trivial solutions? We will prove that a sufficient condition is given by m_i,j+m_j,i?0 (1?i,j?n); from this result we will derive an elementary proof of the existence theorem for Variational Inequalities in the framework of Monotone Operators.     

Ombres Convexité, régularité et sous-harmonicité

Letf:V→R be a function defined on a subsetV ofR ⁿ ×R ^d let?:x→inf{f(x t);t such that(x t)∈V} denote theshadow off and letΦ={(x t)∈V; f(x t)=?(x)} This paper deals with the characterization of some properties of ? in terms of the infinitesimal behavior off near points ζ∈Φ proving in particular a conjecture of J M Trépreau concerning the cased=1 Characterizations of this type are provided for the convexity the subharmonicity or theC ^{1 1} regularity of ? in the interior ofI={x∈ R ⁿ;εR ^d (x t)∈V} and in theC ^{1 1} case an expression forD ²? is given To some extent an answer is given to the following question: which convex function ?:I→R I interval ?R (resp which function √:I→R of classC ^{1 1}) is the shadow of aC ² functionf:I×R→R?     

Absolutely continuous cocycles over irrational rotations

For homeomorphisms $$\left( {z,w} \right)\mathop \to \limits^{T\varphi } \left( {z . e^{2xi\alpha } ,\varphi \left( z \right)w} \right)$$ (z, w ∈S ¹,α is irrational,?:S ¹→S ¹) of the torusS ¹×S ¹ it is proved thatT? has countable Lebesgue spectrum in the orthocomplement of the eigenfunctions whenever? is absolutely continuous with nonzero topological degree and the derivative of? is of bounded variation. Some other cocycles with bounded variation are studied and generalizations of the above result to certain distal homeomorphisms on finite dimensional tori are presented.     

An interior point potential reduction algorithm for the linear complementarity problem

The linear complementarity problem (LCP) can be viewed as the problem of minimizingx ^T y subject toy=Mx+q andx, y?0. We are interested in finding a point withx ^T y <ε for a givenε > 0. The algorithm proceeds by iteratively reducing the potential function $$f(x,y) = \rho \ln x^T y - \Sigma \ln x_j y_j ,$$ where, for example,ρ=2n. The direction of movement in the original space can be viewed as follows. First, apply alinear scaling transformation to make the coordinates of the current point all equal to 1. Take a gradient step in the transformed space using the gradient of the transformed potential function, where the step size is either predetermined by the algorithm or decided by line search to minimize the value of the potential. Finally, map the point back to the original space. A bound on the worst-case performance of the algorithm depends on the parameterλ ^*=λ^*(M, ε), which is defined as the minimum of the smallest eigenvalue of a matrix of the form $$(I + Y^{ - 1} MX)(I + M^T Y^{ - 2} MX)^{ - 1} (I + XM^T Y^{ - 1} )$$ whereX andY vary over the nonnegative diagonal matrices such thate ^T XYe ?ε andX _jj Y _jj?n ². IfM is a P-matrix,λ ^* is positive and the algorithm solves the problem in polynomial time in terms of the input size, |log ε|, and 1/λ ^*. It is also shown that whenM is positive semi-definite, the choice ofρ = 2n+ \(\sqrt {2n} \) yields a polynomial-time algorithm. This covers the convex quadratic minimization problem.     

Definability in substructure orderings, IV: Finite lattices

Let ${\mathcal{L}}$ be the ordered set of isomorphism types of finite lattices, where the ordering is by embeddability. We study first-order definability in this ordered set. Our main result is that for every finite lattice L, the set {?, ? ^opp} is definable, where ? and ? ^opp are the isomorphism types of L and its opposite (L turned upside down). We shall show that the only non-identity automorphism of ${\mathcal{L}}$ is the map ${\ell \mapsto \ell^{\rm opp}}$ .     

Δ2 degrees without Σ1 induction

In this paper, we study the structure of Turing degrees below 0′ in the theory that is a fragment of Peano arithmetic without Σ₁ induction, with special focus on proper d-r.e. degrees and non-r.e. degrees. We prove:

1. P ^? + BΣ₁ + Exp ? There is a proper d-r.e. degree.
2. P ^? +BΣ₁+ Exp ? IΣ₁ ? There is a proper d-r.e. degree below 0′.
3. P ^? + BΣ₁ + Exp ? There is a non-r.e. degree below 0′.

     

Iterated vanishing cycles

If A ^? is a bounded, constructible complex of sheaves on a complex analytic space X, and ${f : X \rightarrow \mathbb{C}}$ and ${g : X \rightarrow \mathbb{C}}$ are complex analytic functions, then the iterated vanishing cycles φ _g [?1](φ _f [?1]A ^?) are important for a number of reasons. We give a formula for the stalk cohomology H*(φ _g [?1]φ _f [?1]A ^?) _x in terms of relative polar curves, algebra, and Morse modules of A ^?.     

Følner sequences and Hilbert’s Irreducibility Theorem over Q

Letf(X; T ₁, ...,T _n) be an irreducible polynomial overQ. LetB be the set ofb teZ ⁿ such thatf(X;b) is of lesser degree or reducible overQ. Let ?={F _j}{F _j } _j?1 ^∞ be a Følner sequence inZ ⁿ — that is, a sequence of finite nonempty subsetsF _j ?Z ⁿ such that for eachvteZ ⁿ , $\mathop {lim}\limits_{j \to \infty } \frac{{\left| {F_j \cap (F_j + \upsilon )} \right|}}{{\left| {F_j } \right|}} = 1$ Suppose ? satisfies the extra condition that forW a properQ-subvariety ofP ⁿ ?A ⁿ and ?>0, there is a neighborhoodU ofW(R) in the real topology such that $\mathop {lim sup}\limits_{j \to \infty } \frac{{\left| {F_j \cap U} \right|}}{{\left| {F_j } \right|}}< \varepsilon $ whereZ ⁿ is identified withA ⁿ (Z). We prove $\mathop {lim}\limits_{j \to \infty } \frac{{\left| {F_j \cap B} \right|}}{{\left| {F_j } \right|}} = 0$ .     

Additive operators preserving rank-additivity on symmetry matrix spaces

We characterize the additive operators preserving rank-additivity on symmetry matrix spaces. LetS _n(F) be the space of alln×n symmetry matrices over a fieldF with 2,3 ∈F ^*, thenT is an additive injective operator preserving rank-additivity onS _n(F) if and only if there exists an invertible matrixU∈M _n(F) and an injective field homomorphism ? ofF to itself such thatT(X)=cUX ^?U^T, ?X=(x_ij)∈S_n(F) wherec∈F ^*,X ^?=(?(x _ij)). As applications, we determine the additive operators preserving minus-order onS _n(F) over the fieldF.     

On bounds for solutions to nonlinear wave equations in Hilbert space with applications to nonlinear elastodynamics

For the nonlinear wave equationu _tt -Nu +G(t,u, u _t ) = ? in Hilbert space, with associated homogeneous initial data, we show how ana priori bound of the form ∫ ₀ ^T ∥G(τ,u, u _τ)∥² dτ ≤ κ ∫ ₀ ^T ∥?(τ)∥² dτ leads to upper and lower bounds for ∥u∥ in terms of ∥?∥. An application to nonlinear elastodynamics is presented.     

On diversity and stability of unit bases for the Euclidean metric

We prove the existence of a family Ω(n) of 2 ^c (where c is the cardinality of the continuum) subgraphs of the unit distance graph (E ⁿ , 1) of the Euclidean space E ⁿ , n ≥ 2, such that (a) for each graph G ? Ω(n), any homomorphism of G to (E ⁿ , 1) is an isometry of E ⁿ ; moreover, for each subgraph G ₀ of the graph G obtained from G by deleting less than c vertices, less than c stars, and less than c edges (we call such a subgraph reduced), any homomorphism of G ₀ to (E ⁿ , 1) is an isometry (of the set of the vertices of G ₀); (b) each graph G ? Ω(n) cannot be homomorphically mapped to any other graph of the family Ω(n), and the same is true for each reduced subgraph of G.     

On the classification of conditionally integrable evolution systems in (1 + 1) dimensions

We generalize earlier results of Fokas and Liu and find all locally analytic (1 + 1)-dimensional evolution equations of order n that admit an N-shock-type solution with N ≤ n + 1. For this, we develop a refinement of the technique from our earlier work, where we completely characterized all (1+1)-dimensional evolution systems u _t = F (x, t, u, ?u/?x,..., ?ⁿ u/? x ⁿ) that are conditionally invariant under a given generalized (Lie-Bäcklund) vector field Q(x, t, u, ?u/?x,..., ?^k u/?x ^k)?/?u under the assumption that the system of ODEs Q = 0 is totally nondegenerate. Every such conditionally invariant evolution system admits a reduction to a system of ODEs in t, thus being a nonlinear counterpart to quasi-exactly solvable models in quantum mechanics.     

The maximal Fejér operator on the spacesH p (R×···×R)

It is shown that the maximal operator of the Fejér means of a tempered distribution is bounded from thed-dimensional Hardy spaceH _p (R×···×R) toL _p (R ^d ) (1/2<p<∞) and is of weak type (H ₁ ^?i ,L ₁) (i=1,…,d), where the Hardy spaceH ₁ ^?i is defined by a hybrid maximal function. As a consequence, we obtain that the Fejér means of a functionf ∈H ₁ ^?i ?L(logL) ^d?1 converge a.e. to the function in question. Moreover, we prove that the Fejér means are uniformly bounded onH _p (R×···×R) whenever 1/2<p<∞. Thus, in casef ∈H _p (R×···×R) the Fejér means converge tof inH _p (R×···×R) norm. The same results are proved for the conjugate Fejér means, too.     

On diophantine equations of the form {({\boldsymbol x}-{\boldsymbol a}_{\bf 1})({\boldsymbol x}-{\boldsymbol a}_{\bf 2}) \ldots ({\boldsymbol x}-{\boldsymbol a}_{\boldsymbol k}) + {\boldsymbol r} = {\boldsymbol y}^{ \boldsymbol n}}

Erd?s and Selfridge [3] proved that a product of consecutive integers can never be a perfect power. That is, the equation x(x?+?1)(x?+?2)...(x?+?(m???1))?=?y ⁿ has no solutions in positive integers x,m,n where m, n?>?1 and y?∈?Q. We consider the equation $$ (x-a_1)(x-a_2) \ldots (x-a_k) + r = y^n $$ where 0?≤?a ₁?<?a ₂?<???<?a _k are integers and, with r?∈?Q, n?≥?3 and we prove a finiteness theorem for the number of solutions x in Z, y in Q. Following that, we show that, more interestingly, for every nonzero integer n?>?2 and for any nonzero integer r which is not a perfect n-th power for which the equation admits solutions, k is bounded by an effective bound.     

An example of asymmetry of convolution operators

Esistono un gruppo compatto non commutativoG ^～ ed un operatore di convoluzioneT tale che: perp∈[2,4] e perq∈[1,2),T∈L _p ^p (G ^～) eT?L _q ^q (G ^～).     

Moments of Exit Times from Wedges for Non-homogeneous Random Walks with Asymptotically Zero Drifts

We study quantitative asymptotics of planar random walks that are spatially non-homogeneous but whose mean drifts have some regularity. Specifically, we study the first exit time τ _α from a wedge with apex at the origin and interior half-angle α by a non-homogeneous random walk on ?² with mean drift at x of magnitude O(∥x∥^?1) as ∥x∥→∞. This is the critical regime for the asymptotic behaviour: under mild conditions, a previous result of the authors stated that τ _α <∞ a.s. for any α. Here we study the more difficult problem of the existence and non-existence of moments ${\mathbb{E}}[ \tau_{\alpha}^{s}]$ , s>0. Assuming a uniform bound on the walk’s increments, we show that for α<π/2 there exists s ₀∈(0,∞) such that ${\mathbb{E}}[ \tau_{\alpha}^{s}]$ is finite for s<s ₀ but infinite for s>s ₀; under specific assumptions on the drift field, we show that we can attain ${\mathbb{E}}[ \tau_{\alpha}^{s}] = \infty$ for any s>1/2. We show that there is a phase transition between drifts of magnitude O(∥x∥^?1) (the critical regime) and o(∥x∥^?1) (the subcritical regime). In the subcritical regime, we obtain a non-homogeneous random walk analogue of a theorem for Brownian motion due to Spitzer, under considerably weaker conditions than those previously given (including work by Varopoulos) that assumed zero drift.     

Difference Sets in {\mathbb{Z}}_4^m and {\mathbb{F}}_2^{2m}

Let R=GR(4,m) be the Galois ring of cardinality 4^m and let T be the Teichmüller system of R. For every map λ of T into { -1,+1} and for every permutation Π of T, we define a map φ _λ ^Π of Rinto { -1,+1} as follows: if x∈R and if x=a+2b is the 2-adic representation of x with x∈T and b∈T, then φ _λ ^Π (x)=λ(a)+2Tr(Π(a)b), where Tr is the trace function of R . For i=1 or i=-1, define D _i as the set of x in R such thatφ _λ ^Π =i. We prove the following results: 1) D _i is a Hadamard difference set of (R,+). 2) If φ is the Gray map of R into ${\mathbb{F}}_2^{2m}$ , then (D _i) is a difference set of ${\mathbb{F}}_2^{2m}$ . 3) The set of D _i and the set of φ(D _i) obtained for all maps λ and Π, both are one-to-one image of the set of binary Maiorana-McFarland difference sets in a simple way. We also prove that special multiplicative subgroups of R are difference sets of kind D _i in the additive group of R. Examples are given by means of morphisms and norm in R.     

Topological change in mean convex mean curvature flow

Consider the mean curvature flow of an (n+1)-dimensional compact, mean convex region in Euclidean space (or, if n<7, in a Riemannian manifold). We prove that elements of the mth homotopy group of the complementary region can die only if there is a shrinking S ^k ×R ^n?k singularity for some k≤m. We also prove that for each m with 1≤m≤n, there is a nonempty open set of compact, mean convex regions K in R ⁿ⁺¹ with smooth boundary ?K for which the resulting mean curvature flow has a shrinking S ^m ×R ^n?m singularity.     

A short note on the Frobenius norm of the commutator

This note mainly aims to improve the inequality, proposed by Böttcher and Wenzel, giving the upper bound of the Frobenius norm of the commutator of two particular matrices in ? ^n×n . We first propose a new upper bound on basis of the Böttcher and Wenzel’s inequality. Motivated by the method used, the inequality ‖XY ? XY‖ _F ² ≤ 2‖X‖ _F ² ‖Y‖ _F ² is finally improved into $$ \left\| {XY - YX} \right\|_F^2 \leqslant 2\left\| X \right\|_F^2 \left\| Y \right\|_F^2 - 2[tr(X^T Y)]^2 . $$ . In addition, a further improvement is made.     

AnO(\sqrt n L) iteration potential reduction algorithm for linear complementarity problems

This paper proposes an interior point algorithm for a positive semi-definite linear complementarity problem: find an (x, y)∈? ²ⁿ such thaty=Mx+q, (x,y)?0 andx ^T y=0. The algorithm reduces the potential function $$f(x,y) = (n + \sqrt n )\log x^T y - \sum\limits_{i = 1}^n {\log x_i y_i } $$ by at least 0.2 in each iteration requiring O(n ³) arithmetic operations. If it starts from an interior feasible solution with the potential function value bounded by \(O(\sqrt n L)\) , it generates, in at most \(O(\sqrt n L)\) iterations, an approximate solution with the potential function value \( - O(\sqrt n L)\) , from which we can compute an exact solution in O(n ³) arithmetic operations. The algorithm is closely related with the central path following algorithm recently given by the authors. We also suggest a unified model for both potential reduction and path following algorithms for positive semi-definite linear complementarity problems.