Search results for "Combinatorics"
showing 10 items of 1770 documents
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})$.
Central idempotents and units in rational group algebras of alternating groups
1998
Let ℚAn be the group algebra of the alternating group over the rationals. By exploiting the theory of Young tableaux, we give an explicit description of the minimal central idempotents of ℚAn. As an application we construct finitely many generators for a subgroup of finite index in the centre of the group of units of ℚAn.
A code to evaluate prolate and oblate spheroidal harmonics
1998
Abstract We present a code to evaluate prolate ( P n m ( x ), Q n m ( x ); n ≥ m , x > 1) and oblate ( P n m ( ix ), Q n m ( ix ); n ≥ m , x > 0) spheroidal harmonics, that is, spherical harmonics ( n and m integers) for real arguments larger than one and for purely imaginary arguments. We start from the known values (in closed form) of P m m and P m +1 m and we apply the forward recurrence relation over n up to a given degree n = N Max . The Wronskian relating P 's and Q 's, together with the evaluation of the continued fraction for Q m+N staggeredMax m / Q m+N staggeredMax -1 m , allows the calculation of Q m+N staggeredMax m and Q m+N staggeredMax -1 m . Backward recurrence is then appli…