Alessandro Conflitti
Manuscripts and Publications
Journals and other Refereed Publications
- `On Elements of High Order in Finite
Fields', Cryptography and Computational Number Theory,
Progress in Computer Science and Applied Logic vol. 20, Birkhauser,
Basel 2001, 11-14.
AMS Subject Classification: 11T30, 11T06.
Abstract:
We provide a more careful analysis of a construction of elements
high order in finite fields which has recently been proposed by S. Gao.
In particular, we improve and generalize one of his results.
- (with W. D. Banks
and I. E. Shparlinski),
`Character
Sums over Integers with Restricted g-ary Digits',
Illinois J. Math. 46 (2002), 819-836.
AMS Subject Classification: 11L07, 11L15, 11L40, 11N64.
Abstract:
We establish upper bounds for multiplicative character sums
and exponential sums over sets of integers that are described by
various properties of their digits in a fixed base $g \geq 2$.
Our main tools are the Weil and Vinogradov bounds for character
sums and exponential sums. Our results can be applied to study
the distribution of quadratic non-residues and primitive roots
among these sets of integers.
- `
On Computation of the Greatest Common Divisor of Several Polynomials
Over a Finite Field',
Finite Fields Appl. 9 (2003), 423-431.
AMS Subject Classification: 11T06, 11Y16, 68Q25.
Keywords: polynomials over a finite field, greatest common
divisor, probabilistic algorithm.
Abstract:
We propose a probabilistic algorithm to reduce computing the greatest
common divisor of m polynomials over a finite field (which requires
computing m-1 pairwise greatest common divisors) to computing the
greatest common divisor of two polynomials over the same field.
- (with W. D. Banks,
J.
B. Friedlander and I. E.
Shparlinski),
`
Exponential Sums over Mersenne Numbers',
Compositio Math. 140 (2004), 15-30.
AMS Subject Classification: 11L07, 11L20.
Keywords: exponential sums over primes, Mersenne numbers.
Abstract:
We give estimates for exponential sums of the form
$$\sum_{n \leq N}\Lambda(n)\exp(2 \pi i a g^n/m),$$
where m is a positive integer, a and g are integers relatively
prime to m, and $\Lambda$ is the von Mangoldt function.
In particular, our results yield bounds for exponential sums of the
form
$$\sum_{p \leq N}\exp(2 \pi i a M_p/m),$$
where $M_p$ is the Mersenne number $M_p=2^p-1$ for any prime p. We
also estimate some closely related sums, including
$$\sum_{n \leq N}\mu(n)\exp(2 \pi i a g^n/m)$$
and
$$\sum_{n \leq N}\mu^2(n)\exp(2 \pi i a g^n/m),$$
where $\mu$ is the Moebius function.
- (with W. D. Banks
and I. E. Shparlinski),
`Number Theoretic
Designs for Directed Regular Graphs of Small Diameter', SIAM J.
Discrete Math. 17 (2004), 377-383.
AMS Subject Classification: 05C35, 11L07, 11L40.
Keywords: exponential sums, character sums, extremal
problems, graphs.
Abstract:
In 1989, F. R. K. Chung gave a construction for certain directed
h-regular graphs of small diameter. Her construction is based on
finite fields, and the upper bound on the diameter of these graphs is
derived from bounds for certain very short character sums. Here we
present two similar constructions that are based on properties of
discrete logarithms and exponential functions in residue rings modulo a
prime power. Accordingly, we use bounds for certain sums with additive
and multiplicative characters to estimate the diameter of our graphs.
We also give a third construction that avoids the use of bounds for
exponential sums.
- (with I. E.
Shparlinski),
`On the
Multidimensional Distribution of the Subset Sum Generator of
Pseudorandom Numbers', Math. Comp. 73 (2004),
1005-1011.
AMS Subject Classification: Primary 11K45, 11T71,
Secondary 11T23, 94A60.
Keywords: Pseudorandom numbers, Subset sum problem,
Knapsack, Exponential sums.
Abstract:
We show that for a random choice of the parameters, the subset sum
pseudorandom number generator produces a sequence of uniformly and
independently distributed pseudorandom numbers. The result can be
useful for both cryptographic and Quasi Monte Carlo applications and
relies on bounds of exponential sums.
- `
Zeros of Real Symmetric Polynomials', Appl. Math. E-Notes
6 (2006), 219-224.
AMS Subject Classification: 05E05, 12D10.
Keywords: Symmetric polynomials, zero set of multivariate
polynomials, vector subspaces.
Abstract:
We consider a generalization of the symmetric polynomials and we give a
sufficient condition in order to have that their real zero set contains a
vector subspace of a certain dimension, which generalizes a result of
R. Aron, R. Gonzalo and A. Zagorodnyuk. Furthermore, we investigate an
application to elementary symmetric polynomials.
- `The size of
Bruhat intervals between nested involutions in $S_{n}$',
Adv. in Appl. Math. 39 (2007), 76-85.
AMS Subject Classification: 05A15, 05E15, 20F55, 33C05.
Keywords: symmetric group, Bruhat intervals, nested involutions.
Abstract: We build a chain
$$\operatorname{id}=\vartheta_{0} < \vartheta_{1} < \cdots
< \vartheta_{\fl{\frac{n}{2}}-1} < \vartheta_{\fl{\frac{n}{2}}}$$
of nested involutions in the Bruhat ordering of $S_{n}$,
with $\vartheta_{\fl{\frac{n}{2}}}$ the maximal element for the
Bruhat order, and we study the cardinality of the Bruhat intervals
$\left[\vartheta_{j},\vartheta_{k}\right]$ for all
$0 \leq j < k \leq \fl{\frac{n}{2}}$, and the number of
permutations incomparable with $\vartheta_{t}$, for all
$0 \leq t \leq \fl{\frac{n}{2}}$.
- `
Enumeration by associated reflections on Coxeter systems',
J. Algebra 320 (2008), 1083-1098.
AMS Subject Classification: 05A15, 20D60, 20F55.
Keywords: reflections in Coxeter systems,
statistics over Coxeter systems, equidistribution results.
Abstract: We define a family of statistics over a generic
finite Coxeter system indexed by subsets of its reflections set, and we
study the corresponding generating functions, proving that they have a lot
of interesting combinatorial properties. In particular, we prove
equidistribution results, namely we investigate some conditions in order to
have that different subsets have the same associated generating function.
Furthermore, some previous results which hold for the symmetric group,
are extended and generalized to any classical Weyl group.
- `
Boolean Algebras and Spectrum',
Carpathian J. Math. 24 (2008), no. 2, 20-25.
AMS Subject Classification: 05C50, 06A11, 11C20, 15A18, 65F15.
Keywords: Boolean algebras, adjacency matrix, characteristic
polynomial.
Abstract: For any Boolean algebra we prove a nice-looking recursive
formula for the characteristic polynomial of its associated undirected Hasse
graph, from which the computation of the spectrum smoothly follows.
- `
On Whitney numbers of the Order Ideals of Generalized Fences and
Crowns', Discrete Math. 309 (2009), 615-621.
AMS Subject Classification: 05A15, 06A07.
Keywords: fences, order ideals, Whitney numbers.
Abstract:
We solve some recurrences given by E. Munarini and N. Zagaglia Salvi
proving explicit formulas for Whitney numbers of the distributive
lattices of order ideals of the fence poset and crown poset.
Moreover, we get a method to obtain explicit formulas for Whitney
numbers of lattices of order ideals of fences with higher asymmetric
peaks.
- `Enumerating
$S_{n}$ by associated Transpositions and Linear Extensions
of Finite Posets', Discrete Math. 309 (2009),
2020-2041.
AMS Subject Classification: 05A05, 05A15, 05E15, 20F55.
Keywords: generalized Eulerian polynomials,
statistics over the symmetric group, partial linear extensions of posets.
Abstract:
We define a family of statistics over the symmetric group $S_{n}$ indexed
by subsets of the traspositions, and we study the corresponding
generating functions. We show that they have many interesting
combinatorial properties. In particular we prove that any poset of size $n$
corresponds to a subset of traspositions of $S_{n}$, and that the
generating function of the corresponding statistic includes partial linear
extensions of such a poset. We prove equidistribution results, and we
explicitily compute the associated generating functions for several classes
of subsets.
- (with O. Azenhas and
R. Mamede),
`Linear
time equivalence of Littlewood-Richardson coefficient symmetry maps',
Discrete Math. Theor. Comput. Sci. Proceedings, 21st International Conference
on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), (2009), 127-144.
Keywords: Symmetry maps of Littlewood-Richardson coefficients;
conjugation symmetry map; linearly time reduction of Young tableau bijections;
tableau switching; Schützenberger evacuation involution.
Abstract: Benkart, Sottile, and Stroomer have completely characterized
by Knuth and dual Knuth equivalence a Young tableau bijection for the conjugation
symmetry of the Littlewood-Richardson coefficients
$c_{\mu,\nu}^{\lambda}=c_{\mu^t,\nu^t}^{\lambda^t}$.
Tableau-switching provides an algorithm to produce explicitly such bijection. Fulton
has shown that the White and the Hanlon-Sundaram maps are versions of that bijection.
In this paper one shows that this conjugation symmetry map has a very natural version.
A consequence of this latter construction is that using notions of Relative Computational
Complexity we are allowed to show that this conjugation symmetry map is linear in time
reducible to the Schützenberger evacuation involution and reciprocally. Thus the
Benkart-Sottile-Stroomer conjugation symmetry map with the two mentioned versions, the
three versions of the commutative symmetry map, and Schützenberger evacuation
involution are linear in time reducible to each other. This answers a question posed
by Pak and Vallejo.
- `On
the Rank Polynomial and Whitney Numbers of Order Ideals
of a Garland', Ars Combin. 95 (2010), 321-331.
AMS Subject Classification: 05A15, 06A07.
Abstract:
We prove explicit formulas for the rank polynomial and Whitney numbers
of the distributive lattice of order ideals of the garland poset,
ordered by inclusion.
- (with M. J.
Schlosser), `
Noncommutative hypergeometric and basic hypergeometric equations',
J. Nonlinear Math. Phys. 17 (2010), 429-443.
AMS Subject Classification: Primary 33C05, 33D15; Secondary 33C99,
33D99, 34G10, 34K30, 46H99.
Keywords: Noncommutative hypergeometric series,
hypergeometric differential equation.
Abstract: Recently, J. A. Tirao [Proc. Nat. Acad. Sci.
100 (14) (2003), 8138-8141] considered a matrix-valued analogue of
the 2F1 Gauß hypergeometric function
and showed that it is the unique solution of a matrix-valued
hypergeometric equation analytic at z=0 with value I, the
identity matrix, at z=0. We give an independent proof of Tirao's
result, extended to the more general setting of hypergeometric
functions over an abstract unital Banach algebra. We provide a similar
(but more complicated-looking) result for a second type of
noncommutative 2F1 Gauß
hypergeometric function. We further give q-analogues for both types
of noncommutative hypergeometric equations.
- (with O. Azenhas and
R. Mamede),
`Nùmeros (coeficientes) de Littlewood-Richardson e simetrias',
Bol. Soc. Port. Mat.
Número Especial, Actas do Encontro Nacional da SPM, Leiria 2010, 5-14.
Abstract: Os números de Littlewood-Richardson são inteiros
não negativos que dependem de três partições
(μ, ν, λ). Aparecem como coeficientes, por exemplo, na expansão
linear do produto de dois polinómios de Schur, na decomposição do
produto de duas classes de Schubert ou ainda na decomposição do produto
tensorial de duas representações polinomiais irredutíveis do grupo
linear. Por outro lado, enumeram diversos objectos de natureza combinatória como
tableaux de Littlewood-Richardson, puzzles de Knutson-Tao-Woodward e mosaicos de Purbhoo,
entre outros. Obedecem a doze simetrias no sentido em que são invariantes para as
permutações e a transposição simultânea de
μ, ν, λ. Seis delas são, no sentido da complexidade computacional,
fáceis de exibir em qualquer um dos modelos mencionados, constituindo um subgrupo
de índice dois do grupo diedral de ordem doze. As seis restantes fora deste subgrupo,
estão escondidas e são descritas por um único gerador que as reduz,
com custo computacional linear, à involução de Schützenberger.
- (with R. Mamede),
`Bijecções entre partições que não cruzam e
partições que não encaixam', Bol. Soc. Port. Mat.
Número Especial, Actas do Encontro Nacional da SPM, Leiria 2010, 20-27.
Abstract: O número de partições do tipo T que
não cruzam é o n-ésimo número de Catalan (1/(n+1))C(2n,n)
quando T=An-1, o coeficiente binomial C(2n,n) quando T=Bn ou
Cn e a diferença C(2n,n)-C(2(n-1),n-1) quando T=Dn, e
esses números coincidem com o correspondente número de
partições que não encaixam. Nesta comunicação
descrevemos a construção destas partições e exibimos
bijecções entre partições que não cruzam e
partições que não encaixam para todos os grupos de Weyl
clássicos.
- (with R. Mamede),
`On Noncrossing
and Nonnesting Partitions of Type $D$', Ann. Comb.
15 (2011), 637-654.
AMS Subject Classification: 05A18, 05E15.
Keywords: Root systems, noncrossing partitions, nonnesting
partitions, bijection.
Abstract: We present an explicit bijection between noncrossing
and nonnesting partitions of Coxeter systems of type $D$ which preserves
openers, closers and transients.
- (with C. M. da Fonseca,
and R. Mamede),
`The maximal
length of a chain in the Bruhat order for a class of binary matrices',
Linear Algebra Appl. 436 (2012), 753-757.
AMS Subject Classification: 05B20, 06A07, 15A36.
Keywords: Bruhat order, row and column sum vectors, (0,1)-matrices, interchange,
minimal matrix, maximal matrix.
Abstract:
We answer a question by Brualdi and Deaett about the maximal length of a chain in the
Bruhat order for an interesting combinatorial class of binary matrices.
- (with C. M. da Fonseca, and
R. Mamede),
` On the largest
size of an antichain in the Bruhat order for A(2k,k)',
Order (to appear).
AMS Subject Classification: 05B20, 06A07, 15A36.
Keywords: Bruhat order, row and column sum vectors, $(0,1)$--matrices,
antichains.
Abstract:
We discuss a problem proposed by Brualdi and Deaett on the largest size of an antichain
in the Bruhat order for the interesting combinatorial class of binary matrices of A(2k,k).
Preprints and Submitted Papers
- (with O. Azenhas and
R. Mamede),
`On
an index two subgroup of puzzle and Littlewood--Richardson tableau
$\mathbb{Z}_{2} \times \mathbb{S}_{3}$--symmetries', preprint.
Keywords: Littlewood-Richardson coefficients, mosaics,
puzzles, tableaux, action of the dihedral group of cardinality twelve.
Abstract:
We consider an action of the dihedral group $\mathbb Z_2\times \mathbb S_3$ on Littlewood-Richardson
tableaux which carries a linear time action of a subgroup of index two. This index two subgroup action
on Knutson-Tao-Woodward puzzles is the group generated by the puzzle mirror reflections with label
swapping. One shows that, as happens in puzzles, half of the twelve symmetries of Littlewood-Richardson
coefficients may also be exhibited on Littlewood-Richardson tableaux by surprisingly easy maps. The
other hidden half symmetries are given by a remaining generator which enables to reduce those symmetries
to the Schützenberger involution. Purbhoo mosaics are used to map the action of the subgroup of index
two on Littlewood-Richardson tableaux into the group generated by the puzzle mirror reflections with label
swapping. After Pak and Vallejo one knows that Berenstein-Zelevinsky triangles, Knutson-Tao hives and
Littlewood-Richardson tableaux may be put in correspondence by linear algebraic maps. We conclude that,
regarding the symmetries, the behaviour of the various combinatorial models for Littlewood-Richardson
coefficients is similar, and the bijections exhibiting them are in a certain sense unique.
- (with O. Azenhas and
R. Mamede),
`(Multiplicity-free)
Skew Schur functions with interval support', preprint.
AMS Subject Classification: 05A17, 05E05, 05E10, 20C30.
Keywords: Skew Schur functions, ribbons, Littlewood-Richardson
coefficients, multiplicity-free, dominance order, interval support.
Abstract:
It is known that the Schur expansion of a skew Schur function runs
over the interval of partitions, equipped with dominance order, defined
by the least and the most dominant Littlewood-Richardson filling of the
skew shape. We characterize skew Schur functions (and therefore the
product of two Schur functions) which are multiplicity-free and the resulting Schur
expansion runs over the whole interval of partitions, i.e. skew Schur functions having
Littlewood-Richardson coefficients always equal to 1 over the full interval. In addition,
a skew Schur function with a disconnected shape attains the full interval only if its
components are ribbons. We consider strips, and ribbons made either of columns or rows,
and characterise those whose support attains the full interval, i.e. having Littlewood-Richardson
coefficients always positive. Schur function products with all Littlewood-Richardson
coefficients positive are also classified.
Back to my home-page.
Disclaimer: Nothing on this page should be taken to represent the
official views of the University of Coimbra.
