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 ₂F₁ 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 ₂F₁ 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=A_n-1, o coeficiente binomial C(2n,n) quando T=B_n ou C_n e a diferença C(2n,n)-C(2(n-1),n-1) quando T=D_n, 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).

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.
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