# 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_{\left\lfloor{\frac{n}{2}}\right\rfloor-1} < \vartheta_{\left\lfloor{\frac{n}{2}}\right\rfloor}$$ of nested involutions in the Bruhat ordering of $$S_{n}$$, with $$\vartheta_{\left\lfloor{\frac{n}{2}}\right\rfloor}$$ 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 \left\lfloor{\frac{n}{2}}\right\rfloor$$, and the number of permutations incomparable with $$\vartheta_{t}$$, for all $$0 \leq t \leq \left\lfloor{\frac{n}{2}}\right\rfloor$$.
• 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 30 (2013), 255-260.
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).
• (with R. Mamede and E. Tzanaki), Dominant Shi regions with a fixed separating wall: bijective enumeration', Australas. J. Combin. 60 (2014), 198-207.
AMS Subject Classification: 05A17, 05A19, 32S22, 52C35.
Abstract: We present a purely combinatorial proof by means of an explicit bijection, of the exact number of dominant regions having as a separating wall the hyperplane associated to the longest root in the m-extended Shi hyperplane arrangement of type A and dimension n-1.
• (with R. Mamede), Gray codes and lexicographical combinatorial generation for nonnesting and sparse nonnesting set partitions', Theoret. Comput. Sci. (to appear).
AMS Subject Classification: 05A18, 68R05, 68W99, 94B25.
Abstract: We present combinatorial Gray codes and explicit designs of efficient algorithms for lexicographical combinatorial generation of the sets of nonnesting and sparse nonnesting set partitions of length n.

## Preprints and Submitted Papers

• (with R. Mamede), `Gray codes for noncrossing and nonnesting partitions of classical types', preprint.
Abstract: In this paper we present Gray codes for the sets of noncrossing partitions associated with the classical Weyl groups, and for the set of nonnesting partitions of type $$B$$. An algorithm for the generation of type $$D$$ nonnesting partitions is developed in which a Gray code is given for those partitions having a zero-block, while the remaining are arranged in lexicographical order.

Back to my home-page.

Disclaimer: The inclusion of any link from this webpage to an external site does not constitute endorsement or recommendation of that site. The author of the current webpage bears no responsibility for the nature, accuracy, legality, content or opinions on external websites referenced herein.

 Website made with a text editor