Search

We study $\ell$-isogeny graphs of ordinary elliptic curves defined over $\mathbb{F}_q$ with an added level structure. Given an integer $N$ coprime to $p$ and $\ell,$ we look at the graphs obtained by adding $\Gamma_0(N),$ $\Gamma_1(N),$ and $\Gamma(N)$-level structures to volcanoes. Given an order $\mathcal{O}$ in an imaginary quadratic field $K,$ we look at the action of generalised ideal class groups of $\mathcal{O}$ on the set of elliptic curves whose endomorphism rings are $\mathcal{O}$ along with a given level structure. We show how the structure of the craters of these graphs is determined by the choice of parameters.

We improve recent results of D. Gomez and A. Winterhof (2010) and of A. Ostafe and I. E. Shparlinski (2011) on the Waring problem with Dickson polynomials in the case of prime finite fields. Our approach is based on recent bounds of Kloosterman and Gauss sums due to A. Ostafe, I. E. Shparlinski and J. F. Voloch (2021).

In this paper, we consider how probability theory can be used to determine the survival strategy in two of the ``Squid Game" and ``Squid Game: The Challenge" challenges: the Hopscotch and the Warships. We show how Hopscotch can be easily tackled with the knowledge of the binomial distribution, taught in introductory statistics courses, while Warships is a much more complex problem, which can be tackled at different levels., Comment: 10 pages, 5 figures

Using well-known mathematical problems for encryption is a widely used technique because they are computationally hard and provide security against potential attacks on the encryption method. The subset sum problem (SSP) can be defined as finding a subset of integers from a given set, whose sum is equal to a specified integer. The classic SSP has various variants, one of which is the multiple-subset problem (MSSP). In the MSSP, the goal is to select items from a given set and distribute them among multiple bins, en-suring that the capacity of each bin is not exceeded while maximizing the total weight of the selected items. This approach addresses a related problem with a different perspective. Here a related different kind of problem is approached: given a set of sets A={A1, A2..., An}, find an integer s for which every subset of the given sets is summed up to, if such an integer exists. The problem is NP-complete when considering it as a variant of SSP. However, there exists an algorithm that is relatively efficient for known pri-vate keys. This algorithm is based on dispensing non-relevant values of the potential sums. In this paper we present the encryption scheme based on MSSP and present its novel usage and implementation in communication.

Let $C$ and $C'$ be curves over a finite field $K$, provided with embeddings $\iota$ and $\iota'$ into their Jacobian varieties. Let $D\to C$ and $D'\to C'$ be the pullbacks (via these embeddings) of the multiplication-by-$2$ maps on the Jacobians. We say that $(C,\iota)$ and $(C',\iota')$ are \emph{doubly isogenous} if $\mathrm{Jac}(C)$ and $\mathrm{Jac}(C')$ are isogenous over $K$ and $\mathrm{Jac}(D)$ and $\mathrm{Jac}(D')$ are isogenous over~$K$. When we restrict attention to the case where $C$ and $C'$ are curves of genus $2$ whose groups of $K$-rational automorphisms are isomorphic to the dihedral group $D_6$ of order $12$, we find many more doubly isogenous pairs than one would expect from reasonable heuristics. Our analysis of this overabundance of doubly isogenous curves over finite fields leads to the construction of a pair of doubly isogenous curves over a number field. That such a global example exists seems extremely surprising. We show that the Zilber--Pink conjecture implies that there can only be finitely many such examples. When we exclude reductions of this pair of global curves in our counts, we find that the data for the remaining curves is consistent with our original heuristic. Computationally, we find that doubly isogenous curves in our family of $D_6$ curves can be distinguished from one another by considering the isogeny classes of the Prym varieties of certain unramified covers of exponent $3$ and $4$. We discuss how our family of curves can be potentially be used to obtain a deterministic polynomial-time algorithm to factor univariate polynomials over finite fields via an argument of Kayal and Poonen., Comment: 40 pages

For a variety over a global field, one can consider subsets of the set of adelic points of the variety cut out by finite abelian descent or Brauer-Manin obstructions. Given a Galois extension of the ground field one can consider similar sets over the extension and take Galois invariants. In this paper, we study under which circumstances the Galois invariants recover the obstruction sets over the ground field. As an application of our results, we study finite abelian descent and Brauer-Manin obstructions for isotrivial curves over function fields and extend results obtained by the first and last authors for constant curves to the isotrivial case.

We study some properties of the lattices defined as the kernel of the map $(a_1,\ldots, a_{q-1}) \mapsto \prod (1-c_ix)^{a_i} \in (\mathbb{F}_q[x]/(x^e))^*$, where $\mathbb{F}_q^* = \{c_1,\ldots,c_{q-1}\}$., Comment: Main result is a special case of a 1999 result of K. Lauter

We prove that the set of rational points on a nonisotrivial curves of genus at least 2 over a global function field is equal to the set of adelic points cut out by the Brauer-Manin obstruction., Comment: With an appendix by Damian R\"ossler

Let $C$ and $D$ be smooth, proper and geometrically integral curves over a finite field $F$. Any morphism from $D$ to $C$ induces a morphism of their \'etale fundamental groups. The anabelian philosophy proposed by Grothendieck suggests that, when $C$ has genus at least $2$, all open homomorphisms between the \'etale fundamental groups should arise in this way from a nonconstant morphism of curves. We relate this expectation to the arithmetic of the curve $C_K$ over the global function field $K = F(D)$. Specifically, we show that there is a bijection between the set of conjugacy classes of well-behaved morphism of fundamental groups and locally constant adelic points of $C_K$ that survive \'etale descent. We use this to provide further evidence for the anabelian conjecture by relating it to another recent conjecture by Sutherland and the second author.

We obtain new bounds on short Weil sums over small multiplicative subgroups of prime finite fields which remain nontrivial in the range the classical Weil bound is already trivial. The method we use is a blend of techniques coming from algebraic geometry and additive combinatorics.

Predicting the responses of a cell under perturbations may bring important benefits to drug discovery and personalized therapeutics. In this work, we propose a novel graph variational Bayesian causal inference framework to predict a cell's gene expressions under counterfactual perturbations (perturbations that this cell did not factually receive), leveraging information representing biological knowledge in the form of gene regulatory networks (GRNs) to aid individualized cellular response predictions. Aiming at a data-adaptive GRN, we also developed an adjacency matrix updating technique for graph convolutional networks and used it to refine GRNs during pre-training, which generated more insights on gene relations and enhanced model performance. Additionally, we propose a robust estimator within our framework for the asymptotically efficient estimation of marginal perturbation effect, which is yet to be carried out in previous works. With extensive experiments, we exhibited the advantage of our approach over state-of-the-art deep learning models for individual response prediction.

The problem of how to genetically modify cells in order to maximize a certain cellular phenotype has taken center stage in drug development over the last few years (with, for example, genetically edited CAR-T, CAR-NK, and CAR-NKT cells entering cancer clinical trials). Exhausting the search space for all possible genetic edits (perturbations) or combinations thereof is infeasible due to cost and experimental limitations. This work provides a theoretically sound framework for iteratively exploring the space of perturbations in pooled batches in order to maximize a target phenotype under an experimental budget. Inspired by this application domain, we study the problem of batch query bandit optimization and introduce the Optimistic Arm Elimination ($\mathrm{OAE}$) principle designed to find an almost optimal arm under different functional relationships between the queries (arms) and the outputs (rewards). We analyze the convergence properties of $\mathrm{OAE}$ by relating it to the Eluder dimension of the algorithm's function class and validate that $\mathrm{OAE}$ outperforms other strategies in finding optimal actions in experiments on simulated problems, public datasets well-studied in bandit contexts, and in genetic perturbation datasets when the regression model is a deep neural network. OAE also outperforms the benchmark algorithms in 3 of 4 datasets in the GeneDisco experimental planning challenge., Comment: 22 pages main, 15 pages appendix

Translating the relevance of preclinical models ($\textit{in vitro}$, animal models, or organoids) to their relevance in humans presents an important challenge during drug development. The rising abundance of single-cell genomic data from human tumors and tissue offers a new opportunity to optimize model systems by their similarity to targeted human cell types in disease. In this work, we introduce SystemMatch to assess the fit of preclinical model systems to an $\textit{in sapiens}$ target population and to recommend experimental changes to further optimize these systems. We demonstrate this through an application to developing $\textit{in vitro}$ systems to model human tumor-derived suppressive macrophages. We show with held-out $\textit{in vivo}$ controls that our pipeline successfully ranks macrophage subpopulations by their biological similarity to the target population, and apply this analysis to rank a series of 18 $\textit{in vitro}$ macrophage systems perturbed with a variety of cytokine stimulations. We extend this analysis to predict the behavior of 66 $\textit{in silico}$ model systems generated using a perturbational autoencoder and apply a $k$-medoids approach to recommend a subset of these model systems for further experimental development in order to fully explore the space of possible perturbations. Through this use case, we demonstrate a novel approach to model system development to generate a system more similar to human biology., Comment: Published at the MLDD workshop, ICLR 2022

An important open problem in supersingular isogeny-based cryptography is to produce, without a trusted authority, concrete examples of "hard supersingular curves" that is, equations for supersingular curves for which computing the endomorphism ring is as difficult as it is for random supersingular curves. A related open problem is to produce a hash function to the vertices of the supersingular $\ell$-isogeny graph which does not reveal the endomorphism ring, or a path to a curve of known endomorphism ring. Such a hash function would open up interesting cryptographic applications. In this paper, we document a number of (thus far) failed attempts to solve this problem, in the hope that we may spur further research, and shed light on the challenges and obstacles to this endeavour. The mathematical approaches contained in this article include: (i) iterative root-finding for the supersingular polynomial; (ii) gcd's of specialized modular polynomials; (iii) using division polynomials to create small systems of equations; (iv) taking random walks in the isogeny graph of abelian surfaces; and (v) using quantum random walks., Comment: 34 pages, 8 figures

We consider smooth projective curves C/$\mathbb{F}$ over a finite field and their symmetric squares $C^{(2)}$. For a global function field $K/\mathbb{F}$, we study the $K$-rational points of $C^{(2)}$. We describe the adelic points of $C^{(2)}$ surviving Frobenius descent and how the $K$-rational points fit there. Our methods also lead to an explicit bound on the number of $K$-rational points of $C^{(2)}$ satisfying an additional condition. Some of our results apply to arbitrary constant subvarieties of abelian varieties, however we produce examples which show that not all of our stronger conclusions extend., Comment: 10 pages

We obtain a nontrivial bound on the number of solutions to the equation $$ A^{x_1} + \ldots + A^{x_\nu} = A^{x_{\nu+1}} + \ldots + A^{x_{2\nu}}, \quad 1 \le x_1, \ldots,x_{2\nu} \le \tau, $$ with a fixed $n\times n$ matrix $A$ over a finite field $\mathbb F_q$ of $q$ elements of multiplicative order $\tau$. We give applications of our result to obtaining a new bound of additive character sums with a matrix exponential function, which is nontrivial beyond the square-root threshold. For $n=2$ this equation has been considered by Kurlberg and Rudnick (2001) (for $\nu=2$) and Bourgain (2005) (for large $\nu$) in their study of quantum ergodicity for linear maps over residue rings. Here we use a new approach to improve their results. We also obtain a bound on Kloosterman sums over small subgroups, of size below the square-root threshold., Comment: This paper supersedes our previous submission: arXiv:2108.13146 which is now obsolete

If K/k is a function field in one variable of positive characteristic, we describe a general algorithm to factor one-variable polynomials with coefficients in K. The algorithm is flexible enough to find factors subject to additional restrictions, e.g., to find all roots that belong to a given finite dimensional k-subspace of K more efficiently. It also provides a deterministic polynomial time irreducibility test in small characteristic. We also discuss some applications., Comment: Revised version. Accepted to ANTS XVI

Let $K$ be the function field of a curve over a finite field of odd characteristic. We investigate using $L$-functions of Galois extensions of $K$ to effectively recover $K$. When $K$ is the function field of the projective line with four rational points removed, we show how to use $L$-functions of a ray class field to effectively recover the removed points up to automorphisms of the projective line. When $K$ is the function field of a plane curve, we show how to effectively recover the equation of that curve using $L$-functions of Artin-Schreier extensions of $K$., Comment: 23 pages; comments welcome

Motivated by questions in cryptography, we look for diophantine equations that are hard to solve but for which determining the number of solutions is easy., Comment: Invited talk at ANTS XIV

In this paper, we prove that a smooth hyperbolic projective curve over a finite field can be recovered from L-functions associated to the Hilbert class field of the curve and its constant field extensions. As a consequence, we give a new proof of a result of Mochizuki and Tamagawa that two such curves with isomorphic fundamental groups are themselves isomorphic., Comment: comments welcome

A linear error correcting code is a subspace of a finite-dimensional space over a finite field with a fixed coordinate system. Such a code is said to be locally recoverable with locality $r$ if, for every coordinate, its value at a codeword can be deduced from the value of (certain) $r$ other coordinates of the codeword. These codes have found many recent applications, e.g., to distributed cloud storage. We will discuss the problem of constructing good locally recoverable codes and present some constructions using algebraic surfaces that improve previous constructions and sometimes provide codes that are optimal in a precise sense. The main conceptual contribution of this paper is to consider surfaces fibered over a curve in such a way that each recovery set is constructed from points in a single fiber. This allows us to use the geometry of the fiber to guarantee the local recoverability and use the global geometry of the surface to get a hold on the standard parameters of our codes. We look in detail at situations where the fibers are rational or elliptic curves and provide many examples applying our methods., Comment: Revised version; incorporates suggestions by referees

We perform the stability analysis for a free surface fluid current modeled as two finite layers of constant vorticity, under the action of gravity and absence of surface tension. In the same spirit as Taylor ["Effect of variation in density on the stability of superposed streams of fluid," Proc. R. Soc. A 132, 499 (1931)], a geometrical approach to the problem is proposed, which allows us to present simple analytical criteria under which the flow is stable. A strong destabilizing effect of stratification in density is revealed by comparison with the physical setting where the vorticity interface is also a density interface separating two immiscible fluids with constant densities., Comment: Revised version. Accepted for publication in Physics of Fluids

This paper deals with the following problem. Given a finite extension of fields $\mathbb{L}/\mathbb{K}$ and denoting the trace map from $\mathbb{L}$ to $\mathbb{K}$ by $\mathrm{Tr}$, for which elements $z$ in $\mathbb{L}$, and $a$, $b$ in $\mathbb{K}$, is it possible to write $z$ as a product $x\cdot y$, where $x,y\in \mathbb{L}$ with $\mathrm{Tr}(x)=a, \mathrm{Tr}(y)=b$? We solve most of these problems for finite fields, with a complete solution when the degree of the extension is at least $5$. We also have results for arbitrary fields and extensions of degrees $2,3$ or $4$. We then apply our results to the study of PN functions, semifields, irreducible polynomials with prescribed coefficients, and to a problem from finite geometry concerning the existence of certain disjoint linear sets.

Let $\mathbb{F}$ be a finite field and $C,D$ smooth, geometrically irreducible proper curves over $\mathbb{F}$ and set $K = \mathbb{F}(D)$. We consider Brauer-Manin and abelian descent obstructions to the existence of rational points and to weak approximation for the curve $C \otimes_\mathbb{F} K$. In particular, we show that Brauer-Manin is the only obstruction to weak approximation and the Hasse principle in the case that the genus of $D$ is less than that of $C$. We also show that we can identify the points corresponding to non-constant maps $D \to C$ using Frobenius descents., Comment: v2: Corrected an error in the proof of Lemma 3.2

We describe the structure of Tate-Shafarevich groups of a constant elliptic curves over function fields by exploiting the volcano structure of isogeny graphs of elliptic curves over finite fields.

We obtain new bounds of exponential sums modulo a prime $p$ with binomials $ax^k + bx^n$. In particular, for $k=1$, we improve the bound of Karatsuba (1967) from $O(n^{1/4} p^{3/4})$ to $O\left(p^{3/4} + n^{1/3}p^{2/3}\right)$ for any $n$, and then use it to improve the bound of Akulinichev (1965) from $O(p^{5/6})$ to $O(p^{4/5})$ for $n | (p-1)$. The result is based on a new bound on the number of solutions and of degrees of irreducible components of certain equations over finite fields.

We obtain a new lower bound on the size of value set f(F_p) of a sparse polynomial f in F_p[X] over a finite field of p elements when p is prime. This bound is uniform with respect of the degree and depends on some natural arithmetic properties of the degrees of the monomial terms of f and the number of these terms. Our result is stronger than those which canted be extracted from the bounds on multiplicities of individual values in f(F_p).

For a curve over a global field we consider for which integers d the d-primary part of the Brauer group can obstruct the existence of rational points. We give examples showing it is possible that there is a d-primary obstruction for infinitely many relatively coprime d, and also an example where the odd part of the Brauer group does not obstruct although there is a Brauer-Manin obstruction. These examples demonstrate that a slightly stronger form of a conjecture of Poonen is false, despite being supported by the same heuristic.

Let X and Y be curves over a finite field. In this article we explore methods to determine whether there is a rational map from Y to X by considering L-functions of certain covers of X and Y and propose a specific family of covers to address the special case of determining when X and Y are isomorphic. We also discuss an application to factoring polynomials over finite fields., Comment: 8 pages

We provide an explicit infinite family of integers $m$ such that all the polynomials of ${\mathbb F}_{2^n}[x]$ of degree $m$ have maximal differential uniformity for $n$ large enough. We also prove a conjecture of the third author in these cases.

We construct families of curves which provide counterexamples for a uniform boundedness question. These families generalize those studied previously by several authors. We show, in detail, what fails in the argument of Caporaso, Harris, Mazur that uniform boundedness follows from the Lang conjecture. We also give a direct proof that these curves have finitely many rational points and give explicit bounds for the heights and number of such points., Comment: 9 pages. v2: typos corrected

We extend existing results characterizing Weil-Ch\^atelet divisibility of locally trivial torsors over number fields to global fields of positive characteristic. Building on work of Gonz\'alez-Avil\'es and Tan, we characterize when local-global divisibility holds in such contexts, providing examples showing that these results are optimal. We give an example of an elliptic curve over a global field of characteristic $2$ containing a rational point which is locally divisible by $8$, but is not divisible by $8$ as well as examples showing that the analogous local-global principle for divisibility in the Weil-Ch\^atelet group can also fail., Comment: v2: incorporates helpful feedback from the community