Search results for "combinatoric"
showing 10 items of 1776 documents
A variation on theorems of Jordan and Gluck
2006
Abstract Gluck proved that any finite group G has an abelian subgroup A such that | G : A | is bounded by a polynomial function of the largest degree of the complex irreducible characters of G . This improved on a previous bound of Isaacs and Passman. In this paper, we present a variation of this result that looks at the number of prime factors. All these results, in turn, may be seen as variations on the classical theorem of Jordan on linear groups.
Zu einem Satz von Isaacs �ber das Casus-Irreducibilis Ph�nomen
2000
Let \(\Omega \) be a field (of characteristic 0). A prime p is called “bose” (naughty) if \(\Omega \) contains all p-th roots of unity. In this paper the theorem is proved: Let K be an admissible subfield of \(\Omega \) (i.e. for each prime p K contains all p-th roots of unity lying in \(\Omega \)), a an algebraic element of \(\Omega /K\) which is contained in a repeated radical extension of K lying in \(\Omega \). Furthermore let the normal hull L of a over K be contained in \(\Omega \). Then all prime divisors of \(\mid L : K \mid \) are naughty (and L is a repeated radical extension of K with naughty prime exponents). This result generalises a theorem of Isaacs [1] who treats the case \(…
Asymptotics for the multiplicities in the cocharacters of some PI-algebras
2003
We consider associative PI-algebras over a field of characteristic zero. We study the asymptotic behavior of the sequence of multiplicities of the cocharacters for some significant classes of algebras. We also give a characterization of finitely generated algebras for which this behavior is linear or quadratic.
Varieties with at most quadratic growth
2010
Let V be a variety of non necessarily associative algebras over a field of characteristic zero. The growth of V is determined by the asymptotic behavior of the sequence of codimensions cn(V); n = 1; 2, … and here we study varieties of polynomial growth. Recently, for any real number a, 3 < a < 4, a variety V was constructed satisfying C1n^a < cn(V) < C2n^a; for some constants C1;C2. Motivated by this result here we try to classify all possible growth of varieties V such that cn(V) < Cn^a; with 0 < a < 2, for some constant C. We prove that if 0 < a < 1 then, for n large, cn(V) ≤ 1, whereas if V is a commutative variety and 1 < a < 2, then lim logn cn(V) = 1 o…
Quantum Queries on Permutations
2015
K. Iwama and R. Freivalds considered query algorithms where the black box contains a permutation. Since then several authors have compared quantum and deterministic query algorithms for permutations. It turns out that the case of \(n\)-permutations where \(n\) is an odd number is difficult. There was no example of a permutation problem where quantization can save half of the queries for \((2m+1)\)-permutations if \(m\ge 2\). Even for \((2m)\)-permutations with \(m\ge 2\), the best proved advantage of quantum query algorithms is the result by Iwama/Freivalds where the quantum query complexity is \(m\) but the deterministic query complexity is \((2m-1)\). We present a group of \(5\)-permutati…
Novel patterns for vector mesons from the large-Nc limit
2008
We report on a relation between the decay constants of \rho-like J^{PC}=1^{--} vector mesons, which arises solely from the perturbative analysis of the VV, TT and VT correlators at order \alpha_s^0 in the large-N_c limit. We find f_{V}^T/f_{V}=1/\sqrt{2} for highly excited states together with a pattern of alternation in sign. Quite remarkably, recent lattice determinations reported f_{\rho}^T/f_{\rho}=0.72(2), in excellent agreement with our large-N_c result. This seems to suggest a pattern like f_{Vn}^T/f_{Vn}=(-1)^n/\sqrt{2} for the whole (1^{--}) states. In order to test this conjecture in real QCD we construct a set of spectral sum rules, which turn out to comply nicely with this scena…
Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$
2017
In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly k or l of the n input bits given by an oracle are 1. We find an optimal algorithm (for some cases), and a nontrivial general lower and upper bound on the minimum number of queries to the black box.
Quantum Query Complexity for Some Graph Problems
2004
The paper [4] by H. Buhrman and R. de Wolf contains an impressive survey of solved and open problems in quantum query complexity, including many graph problems. We use recent results by A.Ambainis [1] to prove higher lower bounds for some of these problems. Some of our new lower bounds do not close the gap between the best upper and lower bounds. We prove in these cases that it is impossible to provide a better application of Ambainis’ technique for these problems.
Quantum Algorithm for Dyck Language with Multiple Types of Brackets
2021
We consider the recognition problem of the Dyck Language generalized for multiple types of brackets. We provide an algorithm with quantum query complexity \(O(\sqrt{n}(\log n)^{0.5k})\), where n is the length of input and k is the maximal nesting depth of brackets. Additionally, we show the lower bound for this problem which is \(\varOmega (\sqrt{n}c^{k})\) for some constant c.
The Variation of the Fractional Maximal Function of a Radial Function
2017
Abstract In this article, we study the regularity of the non-centered fractional maximal operator $M_{\beta}$. As the main result, we prove that there exists $C(n,\beta)$ such that if $q=n/(n-\beta)$ and $f$ is radial function, then $\|DM_{\beta}f\|_{L^{q}({\mathbb{R}^n})}\leq C(n,\beta)\|Df\|_{L^{1}({\mathbb{R}^n})}$. The corresponding result was previously known only if $n=1$ or $\beta=0$. Our proofs are almost free from one-dimensional arguments. Therefore, we believe that the new approach may be very useful when trying to extend the result for all $f\in W^{1,1}({\mathbb{R}^n})$.