On the subgroup distance problem

We investigate the computational complexity of finding an element of a permutation group H⊆S_n with minimal distance to a given π∈S_n, for different metrics on S_n. We assume that H is given by a set of generators. In particular, the size of H might be exponential in the input size, so that in general the problem cannot be solved in polynomial time by exhaustive enumeration. For the case of the Cayley Distance, this problem has been shown to be NP-hard, even if H is abelian of exponent two [R.G.E. Pinch, The distance of a permutation from a subgroup of S_n, in: G. Brightwell, I. Leader, A. Scott, A. Thomason (Eds.), Combinatorics and Probability, Cambridge University Press, 2007, pp. 473-479]. We present a much simpler proof for this result, which also works for the Hamming Distance, the l_p distance, Lee’s Distance, Kendall’s tau, and Ulam’s Distance. Moreover, we give an NP-hardness proof for the l_∞ distance using a different reduction idea. Finally, we discuss the complexity of the corresponding fixed-parameter and maximization problems.     

On the Degree of Approximation by Manifolds of Finite Pseudo-Dimension

The pseudo-dimension of a real-valued function class is an extension of the VC dimension for set-indicator function classes. A class of finite pseudo-dimension possesses a useful statistical smoothness property. In [10] we introduced a nonlinear approximation width = which measures the worst-case approximation error over all functions by the best manifold of pseudo-dimension n . In this paper we obtain tight upper and lower bounds on ρ _n (W ^r,d _p , L _q ) , both being a constant factor of n ^-r/d , for a Sobolev class W ^r,d _p , . As this is also the estimate of the classical Alexandrov nonlinear n -width, our result proves that approximation of W ^r,d _p by the family of manifolds of pseudo-dimension n is as powerful as approximation by the family of all nonlinear manifolds with continuous selection operators. March 12, 1997. Dates revised: August 26, 1997, October 24, 1997, March 16, 1998, June 15, 1998. Date accepted: June 25, 1998.     

Asymptotic Distribution of Nodes for Near-Optimal Polynomial Interpolation on Certain Curves in R 2

Let E\subset \Bbb R ^s be compact and let d _n ^E denote the dimension of the space of polynomials of degree at most n in s variables restricted to E . We introduce the notion of an asymptotic interpolation measure (AIM). Such a measure, if it exists , describes the asymptotic behavior of any scheme τ _n ={ \bf x _k,n } _k=1 ^dnE , n=1,2,\ldots , of nodes for multivariate polynomial interpolation for which the norms of the corresponding interpolation operators do not grow geometrically large with n . We demonstrate the existence of AIMs for the finite union of compact subsets of certain algebraic curves in R ² . It turns out that the theory of logarithmic potentials with external fields plays a useful role in the investigation. Furthermore, for the sets mentioned above, we give a computationally simple construction for ``good' interpolation schemes. November 9, 2000. Date revised: August 4, 2001. Date accepted: September 14, 2001.     

p-Adic dynamical systems of Chebyshev polynomials

We study the behaviour of the iterates of the Chebyshev polynomials of the first kind in p-adic fields. In particular, we determine in the field of complex p-adic numbers for p > 2, the periodic points of the p-th Chebyshev polynomial of the first kind. These periodic points are attractive points. We describe their basin of attraction. The classification of finite field extensions of the field of p-adic numbers ? _p , enables one to locate precisely, for any integer ν ≥ 1, the ν-periodic points of T _p : they are simple and the nonzero ones lie in the unit circle of the unramified extension of ? _p , (p > 2) of degree ν. This generalizes a result, stated by M. Zuber in his PhD thesis, giving the fixed points of T _p in the field ? _p , (p > 2). As often happens, we consider separately the case p = 2. Also, if the integer n ≥ 2 is not divisible by p, then any fixed point w of T _n is indifferent in the field of p-adic complex numbers and we give for p ≥ 3, the p-adic Siegel disc around w.     

Rates of Best Uniform Rational Approximation of Analytic Functions by Ray Sequences of Rational Functions

In this paper, problems related to the approximation of a holomorphic function f on a compact subset E of the complex plane C by rational functions from the class of all rational functions of order (n,m) are considered. Let ρ _n,m = ρ _n,m (f;E) be the distance of f in the uniform metric on E from the class . We obtain results characterizing the rate of convergence to zero of the sequence of the best rational approximation { ρ _n,m(n) } _n=0 ^∞ , m(n)/n → θ ∈ (0,1] as n → ∞ . In particular, we give an upper estimate for the liminf _{n →∞} ρ _n,m(n) ^1/(n+m(n)) in terms of the solution to a certain minimum energy problem with respect to the logarithmic potential. The proofs of the results obtained are based on the methods of the theory of Hankel operators. June 16, 1997. Date revised: December 1, 1997. Date accepted: December 1, 1997. Communicated by Ronald A. DeVore.     

On the security analysis of an image scrambling encryption of pixel bit and its improved scheme based on self-correlation encryption

An image scrambling encryption scheme for pixel bits was presented by Ye [Ye GD. Image scrambling encryption algorithm of pixel bit based on chaos map. Pattern Recognit Lett 2010;31:347-54], which can be seen as one kind of typical binary image scrambling encryption considering from the bit-plain of size M × (8N). However, recently, some defects existing in the original image encryption scheme, i.e., Ye’s scheme, have been observed by Li and Lo [Li CQ, Lo KT. Optimal quantitative cryptanalysis of permutation-only multimedia ciphers against plaintext attacks. Signal Process 2011;91:949-54]. In the attack proposed by Li and Lo at least 3 + ⌈log₂(MN)⌉ plain images of size M × N are used to reveal the permutation matrix W = [w(i, k)] (i ∈ {1, 2, … , M}; k ∈ {1, 2, … , 8N}) which can be applied to recover the exact plain image. In the current paper, at first, one type of special plain image/cipher image is used to analyze the security weakness of the original image scrambling scheme under study. The final encryption vectors TM and TN or the decryption vectors TM′ and TN′ are revealed completely according to our attack. To demonstrate the performance of our attack, a quantified comparison is drawn between our attack and the attack proposed by Li and Lo. Compared with Li and Lo’s attack, our attack is more efficient in the general conditions. In particular, when the sizes of images satisfy the condition M = N or M ? 8N, the number of the used plain images/cipher images is at most 9, which is sharply less than 3 + ⌈log₂(MN)⌉ when M and N are of large size. To overcome the weaknesses of the original scheme, in this paper, an improved image scrambling encryption scheme is proposed. In the improved scheme, the idea of the “self-correlation” method is used to resist the chosen-plaintext attack/known-plaintext attack. The corresponding simulations and analyses illustrate that the improved encryption method has good cryptographic properties, and can overcome the weakness of the original image encryption scheme. Finally, farther improvement is briefly presented for the future work.     

Two finiteness theorems for periodic tilings of d-dimensional euclidean space

Consider the d -dimensional euclidean space E ^d . Two main results are presented: First, for any N∈ N, the number of types of periodic equivariant tilings that have precisely N orbits of (2,4,6, . . . ) -flags with respect to the symmetry group Γ , is finite. Second, for any N∈ N, the number of types of convex, periodic equivariant tilings that have precisely N orbits of tiles with respect to the symmetry group Γ , is finite. The former result (and some generalizations) is proved combinatorially, using Delaney symbols, whereas the proof of the latter result is based on both geometric arguments and Delaney symbols. <lsiheader> <onlinepub>7 August, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>20n2p143.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received September 5, 1996, and in revised form January 6, 1997.     

On graphs without crowns with regularμ-subgraphs

Anm-crown is the complete tripartite graphK _{1, 1,m} with parts of order 1, 1,m, and anm-claw is the complete bipartite graphK _1,m with parts of order 1,m, wherem ≥ 3. A vertexa of a graph Γ is calledweakly reduced iff the subgraph {x є Γ ‖a ^⊥ =x ^⊥} consists of one vertex. A graph Γ is calledweakly reduced iff all its vertices are weakly reduced. In the present paper we classify all connected weakly reduced graphs without 3-crowns, all of whose μ-subgraphs are regular graphs of constant nonzero valency. In particular, we generalize the characterization of Grassman and Johnson graphs due to Numata, and the characterization of connected reduced graphs without 3-claws due to Makhnev. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 874–881, June, 2000. This research was supported by the Russian Foundation for Basic Research under grant No. 99-01-00462.     

On the invertibility of the operator <Emphasis Type="Italic">d/dt</Emphasis> + <Emphasis Type="Italic">A</Emphasis> in certain functional spaces

We prove that the operator d/dt + A constructed on the basis of a sectorial operator A with spectrum in the right half-plane of ℂ is continuously invertible in the Sobolev spaces W _p ¹ (ℝ, D _α), α ≥ 0. Here, D _α is the domain of definition of the operator A ^α and the norm in D _α is the norm of the graph of A ^α. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 8, pp. 1020–1025, August, 2007.     

Double Hopf bifurcation and chaos in Liu system with delayed feedback

In this paper, we consider the stability of equilibria,&nbsp;Hopf and&nbsp;double Hopf bifurcation in Liu system with delay&nbsp;feedback. Firstly,&nbsp;we identify the critical values for stability switches and&nbsp;Hopf&nbsp;bifurcationusing the method of bifurcation&nbsp;analysis. When we choose&nbsp;appropriate feedback strength and delay, two symmetrical nontrivial&nbsp;equilibria of Liusystem can be controlled to be stable at the same&nbsp;time, and the stable bifurcating periodic solutions occur in the&nbsp;neighborhood of the two equilibria at the same time. Secondly, by&nbsp;applying the normal form method and center manifold theory,the&nbsp;normal form near the double Hopf bifurcation, as well as&nbsp;classifications of local dynamics are analyzed. Furthermore, we give&nbsp;the bifurcation diagram to illustrate numerically that a family of&nbsp;stable periodic solutions bifurcated from Hopf bifurcation occur in&nbsp;a large region of delay and the Liu system with delay can appear the&nbsp;phenomenon of ``chaos switchover''.     

On the Cocircuit Graph of an Oriented Matroid

In this paper we consider the cocircuit graph G _M of an oriented matroid M , the 1 -skeleton of the cell complex W formed by the span of the cocircuits of M . In general, W is not determined by G _M . However, we show that if the vertex set (resp. edge set) of G _M is properly labeled by the hyperplanes (resp. colines) of M , G _M determines W . Also we prove that, when M is uniform, the cocircuit graph together with all antipodal pairs of vertices being marked determines W . These results can be considered as variations of Blind—Mani's theorem that says the 1-skeleton of a simple convex polytope determines its face lattice. Received August 14, 1998, and in revised form March 2, 1999.     

Group actions on Stanley-Reisner rings and invariants of permutation groups

Let H be a group of permutations of x₁ ,…, x_n and let Q^H[x₁ , x₂ ,…, x_n] denote the ring of H-invariant Polynomials in x₁ , x₂ ,…, x_n with rational coefficients. Combinatorial methods for the explicit construction of free bases for Q^H[x₁ , x₂ ,…, x_n] as a module over the symmetric polynomials are developed. The methods are developed by studying the action of the symmetric group on the Stanley-Reisner ring of the subset lattice. Some general results are also obtained by studying the action of a Coxeter group on the Stanley-Reisner ring of the corresponding Coxeter complex. In the case of a Weyl group, a purely combinatorial construction of certain invariants first considered by R. Steinberg (Topology14 (1975), 173–177) is obtained. Some applications to representation theory are also included.     

On the interpolation of some generalized function spaces of different anisotropy

In the paper, the interpolation properties of the spacesH _p ^s (v; ℝ _n ) of Sobolev-Liouville type and the spacesB _{p, q} ^s (μ ℝ _n ) of Nikol'skii-Besov type generated by functions of polynomial growth that are infinitely differentiable outside of the origin are studied. Interpolation formulas for the pairs {H(v _o ),H(v ₁)} and {B(μ₀),B(μ₁)} of spaces of the above types for which the anisotropies of the interpolated spaces do not depend on each other are proved. The investigated spaces, for certain specification of the generating functions, coincide with the classical (isotropic and anisotropic) Sobolev-Liouville and Nikol'skii-Besov spaces. Translated fromMatematicheskie Zametki, Vol. 62, No. 5, pp. 666–672, November, 1997. Translated by A. I. Shtern     

Edge-Ramsey theory

LetK be a configuration, a set of points in some finite-dimensional Euclidean space. Letn andk be positive integers. The notationR(K, n, r) is an abbreviation for the following statement: For everyr-coloring of the points of then-dimensional Euclidean space,R ⁿ , a monochromatic configurationL which is congruent toK exists. A configurationK is Ramsey if the following holds: For every positive integerr, a positive integern=n(K, r) exists such that, for allm≥n, R(K, m, r) holds. A configuration is spherical if it can be embedded in the surface of a sphere inn-space, providedn is sufficiently large. It is relatively easy to show that if a configuration is Ramsey, it must be spherical. Accordingly, a good fraction of the research efforts in Euclidean Ramsey theory is devoted to determining which spherical configurations are Ramsey. It is known that then-dimensional measure polytopes (the higher-dimensional analogs of a cube), then-dimensional simplex, and the regular polyhedra inR ² andR ³ are Ramsey. Now letE denote a set of edges in a configurationK. The pair (K, E) is called an edge-configuration, andR _e (K, E, n, r) is used as an abbreviation for the following statement: For anyr-coloring of the edges ofR ⁿ , there is an edge configuration (L, F) congruent to (K, E) so that all edges inF are assigned the same color. An edge-configuration isedge-Ramsey if, for allr≥1, a positive integern=n(K, E, r) exists so that ifm≥n, the statementR _e (K, E, m, r) holds. IfK is a regular polytope, it is saidK isedge-Ramsey when the configuration determined by the set of edges of minimum length is edge-Ramsey. It is known that then-dimensional simplex is edge-Ramsey and that the nodes of any edge-Ramsey configuration can be partitioned into two spherical sets. Furthermore, the edges of any edge-Ramsey configuration must all have the same length. It is conjectured that the unit square is edge-Ramsey, and it is natural to ask the more general question: Which regular polytopes are edge-Ramsey? In this article it is shown that then-dimensional measure polytope and then-dimensional cross polytope are edge-Ramsey. It is also shown that these two infinite families and then-dimensional simplexes are the only regular edge-Ramsey polytopes, with the possible exceptions of the hexagon and the 24-cell.     

On the Stabilization of a Solution of the Cauchy Problem for One Class of Integro-Differential Equations

We consider a solution of the Cauchy problem u(t, x), t > 0, x ∈ R ², for one class of integro-differential equations. These equations have the following specific feature: the matrix of the coefficients of higher derivatives is degenerate for all x. We establish conditions for the existence of the limit lim _t→∞ u(t, x) = v(x) and represent the solution of the Cauchy problem in explicit form in terms of the coefficients of the equation.__________Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 56, No. 12, pp. 1699 – 1706, December, 2004.     

Rate of convergence for Szász-Bézier operators

We estimate the rate of convergence for functions of bounded variation for the Bézier variant of the Szász operators S _n,α (f,x). We study the rate of convergence of S _n,α (f,x) in the case 0 < α < 1. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 57, No. 12, pp. 1619–1624, December, 2005.     

Momentopes, the Complexity of Vector Partitioning, and Davenport—Schinzel Sequences

The computational complexity of the partition problem , which concerns the partitioning of a set of n vectors in d -space into p parts so as to maximize an objective function which is convex on the sum of vectors in each part, is determined by the number of vertices of the corresponding p-partition polytope defined to be the convex hull in (d\times p) -space of all solutions. In this article, introducing and using the class of Momentopes , we establish the lower bound v _p,d (n)=Ω(n^ \lfloor (d-1)/2 \rfloor p ) on the maximum number of vertices of any p -partition polytope of a set of n points in d -space, which is quite compatible with the recent upper bound v _p,d (n)=O(n ^d(p-1)-1 ) , implying the same bound on the complexity of the partition problem. We also discuss related problems on the realizability of Davenport—Schinzel sequences and describe some further properties of Momentopes. Received April 4, 2001, and in revised form October 3, 2001. Online publication February 28, 2002.     

<Emphasis Type="Italic">∂</Emphasis>-operations and <Emphasis Type="Italic">H</Emphasis><Subscript><Emphasis Type="Italic">V</Emphasis></Subscript>-fields

The hyperoperations, called theta-operations （δ）, are motivated from the usual property, which the derivative has on the derivation of a product of functions. Using any map on a set, one can define δ-operations. In this paper, we continue our study on the δ-operations on groupoids, rings, fields and vector spaces or on the corresponding hyperstructures. Using δ-operations one obtains, mainly, Hwstructures, which form the largest class of the hyperstructures. For representation theory of hyperstructures, by hypermatrices, one needs special Hv-rings or Hy-fields, so these hyperstructures can be used. Moreover, we study the relation of these δ-structures with other classes of hyperstructures, especially with the Hv-structures.     

Differential-geometric structures on generalized Reidemeister and Bol three-webs

In this paper, we present the main results of the study of multidimensional three-websW(p, q, r) obtained by the method of external forms and moving Cartan frame. The method was developed by the Russian mathematicians S. P. Finikov, G. F. Laptev, and A. M. Vasiliev, while fundamentals of differential-geometric (p, q, r)-webs theory were described by M. A. Akivis and V. V. Goldberg. Investigation of (p, q, r)-webs, including algebraic and geometric theory aspects, has been continued in our papers, in particular, we found the structure equations of a three-web W(p, q, r), where p = λl, q = λm, and r = λ(l + m − 1). For such webs, we define the notion of a generalized Reidemeister configuration and proved that a three-web W(λl, λm, λ(l + m − 1)), on which all sufficiently small generalized Reidemeister configurations are closed, is generated by a λ-dimensional Lie group G. The structure equations of the web are connected with the Maurer–Cartan equations of the group G. We define generalized Reidemeister and Bol configurations for three-webs W(p, q, q). It is proved that a web W(p, q, q) on which generalized Reidemeister or Bol configurations are closed is generated, respectively, by the action of a local smooth q-parametric Lie group or a Bol quasigroup on a smooth p-dimensional manifold. For such webs, the structure equations are found and their differential-geometric properties are studied.     

Normal Spreads

In Dedicata 16 (1984), pp. 291–313, the representation of Desarguesian spreads of the projective space PG(2t – 1, q) into the Grassmannian of the subspaces of rank t of PG(2t – 1, q) has been studied. Using a similar idea, we prove here that a normal spread of PG(rt – 1,q) is represented on the Grassmannian of the subspaces of rank t of PG(rt – 1, q) by a cap V _{r, t} of PG(r ^t – 1, q), which is the GF(q)-scroll of a Segre variety product of t projective spaces of dimension (r – 1), and that the collineation group of PG(r ^t – 1, q) stabilizing V _{r, t} acts 2-transitively on V _{r, t} . In particular, we prove that V _{3, 2} is the union of q ² – q + 1 disjoint Veronese surfaces, and that a Hermitan curve of PG(2, q ²) is represented by a hyperplane section U of V _{3, 2}. For q 0,2 (mod 3) the algebraic variety U is the unitary ovoid of the hyperbolic quadric Q ⁺ (7, q) constructed by W. M. Kantor in Canad. J. Math., 5 (1982), 1195–1207. Finally we study a class of blocking sets, called linear, proving that many of the known examples of blocking sets are of this type, and we construct an example in PG(3, q ²). Moreover, a new example of minimal blocking set of the Desarguesian projective plane, which is linear, has been constructed by P. Polito and O. Polverino.