On collineation groups of finite projective spaces containing a Singer cycle

By a result of Kantor, any subgroup of GL(n, q) containing a Singer cycle normalizes a field extension subgroup. This result has as a consequence a projective analogue, and this paper gives the details of this deduction, showing that any subgroup of PΓL(n, q) containing a projective Singer cycle normalizes the image of a field extension subgroup GL(n/s, q^s) under the canonical homomorphism GL(n, q) → PGL(n, q), for some divisor s of n, and so is contained in the image of ΓL(n/s, q^s) under the canonical homomorphism ΓL(n, q) → PΓL(n, q). The actions of field extension subgroups on V (n, q) are also investigated. In particular, we prove that any field extension subgroup GL(n/s, q^s) of GL(n, q) has a unique orbit on s-dimensional subspaces of V (n, q) of length coprime to q. This orbit is a Desarguesian s-partition of V (n, q).     

Optimal adaptive sampling recovery

We propose an approach to study optimal methods of adaptive sampling recovery of functions by sets of a finite capacity which is measured by their cardinality or pseudo-dimension. Let W???L _q , 0?q?≤?∞?, be a class of functions on \({{\mathbb I}}^d:= [0,1]^d\). For B a subset in L _q , we define a sampling recovery method with the free choice of sample points and recovering functions from B as follows. For each f?∈?W we choose n sample points. This choice defines n sampled values. Based on these sampled values, we choose a function from B for recovering f. The choice of n sample points and a recovering function from B for each f?∈?W defines a sampling recovery method \(S_n^B\) by functions in B. An efficient sampling recovery method should be adaptive to f. Given a family \({\mathcal B}\) of subsets in L _q , we consider optimal methods of adaptive sampling recovery of functions in W by B from \({\mathcal B}\) in terms of the quantity

$ R_n(W, {\mathcal B})_q := \ \inf_{B \in {\mathcal B}}\, \sup_{f \in W} \, \inf_{S_n^B} \, \|f - S_n^B(f{\kern1pt})\|_q. $

Denote \(R_n(W, {\mathcal B})_q\) by e _n (W) _q if \({\mathcal B}\) is the family of all subsets B of L _q such that the cardinality of B does not exceed 2 ⁿ , and by r _n (W) _q if \({\mathcal B}\) is the family of all subsets B in L _q of pseudo-dimension at most n. Let 0?p,q , θ?≤?∞ and α satisfy one of the following conditions: (i) α?>?d/p; (ii) α?=?d/p, θ?≤?min (1,q), p,q?d-variable Besov class \(U^\alpha_{p,\theta}\) (defined as the unit ball of the Besov space \(B^\alpha_{p,\theta}\)), there is the following asymptotic order

$ e_n\big(U^\alpha_{p,\theta}\big)_q \ \asymp \ r_n\big(U^\alpha_{p,\theta}\big)_q \ \asymp \ n^{- \alpha / d} . $

To construct asymptotically optimal adaptive sampling recovery methods for \(e_n(U^\alpha_{p,\theta})_q\) and \(r_n(U^\alpha_{p,\theta})_q\) we use a quasi-interpolant wavelet representation of functions in Besov spaces associated with some equivalent discrete quasi-norm.

     

Seifert manifolds and (1, 1)-knots

The aim of this paper is to investigate the relations between Seifert manifolds and (1, 1)-knots. In particular, we prove that each orientable Seifert manifold with invariants

$\{ Oo,0| - 1;\underbrace {(p,q),...,(p,q)}_{n times},(l,l - 1)\} $

has the fundamental group cyclically presented by G _n ((x ₁ ^q ...x _n ^{q l} x _n ^?p ) and, moreover, it is the n-fold strongly-cyclic covering of the lens space L(|nlq ? p|, q) which is branched over the (1, 1)-knot K(q, q(nl ? 2), p ? 2q, p ? q) if p ≥ 2q and over the (1, 1)-knot K(p? q, 2q ? p, q(nl ? 2), p ? q) if p< 2q.

     

A Note on MDS Codes, <Emphasis Type="Italic">n</Emphasis>-Arcs and Complete Designs

A generalized incidence matrix of a design over GF(q) is any matrix obtained from the (0, 1)-incidence matrix by replacing ones with nonzero elements from GF(q). The dimension d _q of a design D over GF(q) is defined as the minimum value of the q-rank of a generalized incidence matrix of D. It is proved that the dimension d _q of the complete design on n points having as blocks all w-subsets, is greater that or equal to n ? w + 1, and the equality d _q = n ? w + 1 holds if and only if there exists an [n, n ? w + 1, w] MDS code over GF(q), or equivalently, an n-arc in PG(w ? 2, q).     

On the pronormality of subgroups of odd index in finite simple symplectic groups

A subgroup H of a group G is pronormal if the subgroups H and H ^g are conjugate in 〈H,H ^g 〉 for every g ∈ G. It was conjectured in [1] that a subgroup of a finite simple group having odd index is always pronormal. Recently the authors [2] verified this conjecture for all finite simple groups other than PSL _n (q), PSU _n (q), E ₆(q), ² E ₆(q), where in all cases q is odd and n is not a power of 2, and P Sp_2n (q), where q ≡ ±3 (mod 8). However in [3] the authors proved that when q ≡ ±3 (mod 8) and n ≡ 0 (mod 3), the simple symplectic group P Sp²ⁿ (q) has a nonpronormal subgroup of odd index, thereby refuted the conjecture on pronormality of subgroups of odd index in finite simple groups.The natural extension of this conjecture is the problem of classifying finite nonabelian simple groups in which every subgroup of odd index is pronormal. In this paper we continue to study this problem for the simple symplectic groups P Sp_2n (q) with q ≡ ±3 (mod 8) (if the last condition is not satisfied, then subgroups of odd index are pronormal). We prove that whenever n is not of the form 2 ^m or 2 ^m (2^2k +1), this group has a nonpronormal subgroup of odd index. If n = 2 ^m , then we show that all subgroups of P Sp_2n (q) of odd index are pronormal. The question of pronormality of subgroups of odd index in P Sp_2n (q) is still open when n = 2 ^m (2^2k + 1) and q ≡ ±3 (mod 8).     

Estimation of the depth of reversible circuits consisting of NOT,CNOT and 2-CNOT gates

The paper discusses the asymptotic depth of a reversible circuits consisting of NOT, CNOT and 2-CNOT gates. The reversible circuit depth function D(n, q) is introduced for a circuit implementing a mapping f: Z₂ⁿ → Z₂ⁿ as a function of n and the number q of additional inputs. It is proved that for the case of implementation of a permutation from A(Z₂ⁿ) with a reversible circuit having no additional inputs the depth is bounded as D(n, 0) ? 2ⁿ/(3log₂n). It is also proved that for the case of transformation f: Z₂ⁿ → Z₂ⁿ with a reversible circuit having q₀ ~ 2ⁿ additional inputs the depth is bounded as D(n,q₀) ? 3n.     

Hochschild cohomology ring modulo nilpotence of a one point extension of a quiver algebra defined by two cycles and a quantum-like relation

We consider a one point extension algebra B of a quiver algebra A _q over a field k defined by two cycles and a quantum-like relation depending on a nonzero element q in k. We determine the Hochschild cohomology ring of B modulo nilpotence and show that if q is a root of unity, then B is a counterexample to Snashall-Solberg’s conjecture.     

The product of octahedra is badly approximated in the <Emphasis Type="Italic">ℓ</Emphasis><Subscript>2,1</Subscript>-metric

We prove that the Cartesian product of octahedra B _1,∞ ^n,m = B ₁ ⁿ ×···× B ₁ ⁿ (m factors) is poorly approximated by spaces of half dimension in the mixed norm: d _N/2(B _1,∞ ^n,m , ? _2,1 ^n,m ) ≥ cm, N = mn. As a corollary, we find the order of linear widths of the Hölder–Nikol’skii classes H _p ^r (T ^d ) in the metric of L _q in certain domains of variation of the parameters (p, q).     

Carleson measures,BMO spaces and balayages associated to Schrdinger operators

Let L be a Schrdinger operator of the form L =-? + V acting on L~2(R~n), n≥3, where the nonnegative potential V belongs to the reverse Hlder class B_q for some q≥n. Let BMO_L(R~n) denote the BMO space associated to the Schrdinger operator L on R~n. In this article, we show that for every f ∈ BMO_L(R~n) with compact support, then there exist g ∈ L~∞(R~n) and a finite Carleson measure μ such that f(x) = g(x) + S_(μ,P)(x) with ∥g∥∞ + |||μ|||c≤ C∥f∥BMO_L(R~n), where S_(μ,P)=∫(R_+~(n+1))Pt(x,y)dμ(y, t),and Pt(x, y) is the kernel of the Poisson semigroup {e-~(t(L)~(1/2))}t0 on L~2(R~n). Conversely, if μ is a Carleson measure, then S_(μ,P) belongs to the space BMO_L(R~n). This extends the result for the classical John-Nirenberg BMO space by Carleson(1976)(see also Garnett and Jones(1982), Uchiyama(1980) and Wilson(1988)) to the BMO setting associated to Schrdinger operators.     

General Hausdorff functions,and the notion of one-sided measure and dimension

The main facts about Hausdorff and packing measures and dimensions of a Borel set E are revisited, using determining set functions \(\phi_\alpha\colon\mathcal{B}_E\to(0,\infty)\), where \(\mathcal{B}_E\) is the family of all balls centred on E and α is a real parameter. With mild assumptions on φ_α, we verify that the main density results hold, as well as the basic properties of the corresponding box dimension. Given a bounded open set V in ? ^D , these notions are used to introduce the interior and exterior measures and dimensions of any Borel subset of ?V. We stress that these dimensions depend on the choice of φ_α. Two determining functions are considered, φ_α(B)=Vol _D (B∩V)diam(B)^α-D and φ_α(B)=Vol _D (B∩V)^α/D , where Vol _D denotes the D-dimensional volume.     

Inversion and subspaces of a finite field

Consider two F _q -subspaces A and B of a finite field, of the same size, and let A ^?1 denote the set of inverses of the nonzero elements of A. The author proved that A ^?1 can only be contained in A if either A is a subfield, or A is the set of trace zero elements in a quadratic extension of a field. Csajbók refined this to the following quantitative statement: if A ^?1 ? B, then the bound |A ^?1∩B| ≤ 2|B|/q ? 2 holds. He also gave examples showing that his bound is sharp for |B| ≤ q ³. Our main result is a proof of the stronger bound |A ^?1 ∩ B| ≤ |B|/q · (1 + O _d (q ^?1/2)), for |B| = q ^d with d > 3. We also classify all examples with |B| ≤ q ³ which attain equality or near-equality in Csajbók’s bound.     

Equalities on the number of conjugacy classes of the Sylow p-subgroups of GL(n,q)

We denote by Gn the group of the upper unitriangular matrices over F_q, the finite field with q = p^t elements, and r(G_n) the number of conjugacy classes of G_n. In this paper, we obtain the value of r(G_n) modulo (q² -1)(q -1). We prove the following equalities     

Designs associated with maximum independent sets of a graph

A (v, β _o , μ)-design over regular graph G = (V, E) of degree d is an ordered pair D = (V, B), where |V| = v and B is the set of maximum independent sets of G called blocks such that if i, j ∈ V, i ≠ j and if i and j are not adjacent in G then there are exactly μ blocks containing i and j. In this paper, we study (v, β _o , μ)-designs over the graphs K _n × K _n , T(n)-triangular graphs, L ₂(n)-square lattice graphs, Petersen graph, Shrikhande graph, Clebsch graph and the Schläfli graph and non-existence of (v, β _o , μ)-designs over the three Chang graphs T ₁(8), T ₂(8) and T ₃(8).     

Complexity of function systems over a finite field in the class of polarized polynomial forms

The Shannon complexity of a function system over a q-element finite field which contains m functions of n variables in the class of polarized polynomial forms is exactly evaluated: L _q ^PPF (n,m) = q ⁿ for all n ≥ 1, m ≥ 2, and all possible odd q. It has previously been known that L₂^PPF (n,m) = 2 ⁿ and L₃^PPF (n,m) = 3 ⁿ for all n ≥ 1 and m ≥ 2.     

On the phase transitions of (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)-SAT

Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let T _k (V) denote the set of all 2 ^k n ^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in T _k (V) independently with probability p, and let Q be a given set of q “bad” tuple assignments. An instance I = (C,Q) is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tuple assignment in Q. Suppose that θ, q > 0 are fixed and ε = ε(n) > 0 be such that εlnn/lnlnn→∞. Let k ≥ (1 + θ) log₂ n and let \({p_0} = \frac{{\ln 2}}{{q{n^{k - 1}}}}\). We prove that

$$\mathop {\lim }\limits_{n \to \infty } P\left[ {I is satisfiable} \right] = \left\{ {\begin{array}{*{20}c} {1,} & {p \leqslant (1 - \varepsilon )p_0 ,} \\ {0,} & {p \geqslant (1 + \varepsilon )p_0 .} \\ \end{array} } \right.$$

     

Note edge-colourings of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n,n</Emphasis></Subscript> with no long two-coloured cycles

Consider the set of all proper edge-colourings of a graph G with n colours. Among all such colourings, the minimum length of a longest two-coloured cycle is denoted L(n, G). The problem of understanding L(n, G) was posed by Häggkvist in 1978 and, specifically, L(n, K _n,n ) has received recent attention. Here we construct, for each prime power q ≥ 8, an edge-colouring of K _n,n with n colours having all two-coloured cycles of length ≤ 2q ², for integers n in a set of density 1 ? 3/(q ? 1). One consequence is that L(n, K _n,n ) is bounded above by a polylogarithmic function of n, whereas the best known general upper bound was previously 2n ? 4.     

Properties of element orders in covers for L<Subscript>n</Subscript>(<Emphasis Type="Italic">q</Emphasis>) and U<Subscript>n</Subscript>(<Emphasis Type="Italic">q</Emphasis>)

We show that if a finite simple group G, isomorphic to PSL_n(q) or PSU_n(q) where either n ≠ 4 or q is prime or even, acts on a vector space over a field of the defining characteristic of G; then the corresponding semidirect product contains an element whose order is distinct from every element order of G. We infer that the group PSL_n(q), n ≠ 4 or q prime or even, is recognizable by spectrum from its covers thus giving a partial positive answer to Problem 14.60 from the Kourovka Notebook.     

Nonlinear trigonometric approximations of multivariate function classes

Order-sharp estimates are established for the best N-term approximations of functions from Nikol’skii–Besov type classes B_pq^sm(T^k) with respect to the multiple trigonometric system T^(k) in the metric of L_r(T^k) for a number of relations between the parameters s, p, q, r, and m (s = (s₁,..., s_n) ∈ R₊ⁿ, 1 ≤ p, q, r ≤ ∞, m = (m₁,..., m_n) ∈ Nⁿ, k = m₁ +... + m_n). Constructive methods of nonlinear trigonometric approximation—variants of the so-called greedy algorithms—are used in the proofs of upper estimates.     

On <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis>,<Emphasis Type="Italic">q</Emphasis></Subscript>-factorization of complete bipartite multigraphs

Let λK _m,n be a complete bipartite multigraph with two partite sets having m and n vertices, respectively. A K _p,q -factorization of λK _m,n is a set of edge-disjoint K _p,q -factors of λK _m,n which partition the set of edges of λK _m,n . When p = 1 and q is a prime number, Wang, in his paper [On K _1,q -factorization of complete bipartite graph, Discrete Math., 126: (1994), 359-364], investigated the K _1,q -factorization of K _m,n and gave a sufficient condition for such a factorization to exist. In papers [K _1,k -factorization of complete bipartite graphs, Discrete Math., 259: 301-306 (2002),; K _p,q -factorization of complete bipartite graphs, Sci. China Ser. A-Math., 47: (2004), 473-479], Du and Wang extended Wang’s result to the case that p and q are any positive integers. In this paper, we give a sufficient condition for λK _m,n to have a K _p,q -factorization. As a special case, it is shown that the necessary condition for the K _p,q -factorization of λK _m,n is always sufficient when p : q = k : (k + 1) for any positive integer k.     

Riesz Transforms Associated with Higher-Order Schrödinger Type Operators

Let L = L ₀ + V be a Schrödinger type operator, where L ₀ is a higher order elliptic operator with bounded complex coefficients in divergence form and V is a signed measurable function. Under the strongly subcritical assumption on V, we study the L ^q boundedness of Riesz transform ? ^m L ^?1/2 for q ≤ 2 based on the off-diagonal estimates of semigroup e ^{?t L} . Furthermore, the authors impose extra regularity assumptions on V to obtain the L ^q boundedness of Riesz transform ? ^m L ^?1/2 for some q > 2. In particular, these results are applied to the more interesting Schrödinger operators L = P(D) + V, where P(D) is any homogeneous positive elliptic operator with constant coefficients.