In this paper we study the restriction estimate for the flat disk over finite fields. Mockenhaupt and Tao initially studied this problem but their results were addressed only for dimensions n=4,6. We ...improve and extend their results to all dimensions n≥6. More precisely, we obtain the sharp L2→Lr estimates, which cannot be proven by applying the usual Stein-Tomas argument over a finite field even with the optimal Fourier decay estimate on the flat disk. One of main ingredients is to discover and analyze an explicit form of the Fourier transform of the surface measure on the flat disk. In addition, based on the recent results on the restriction estimates for the paraboloids, we address improved restriction estimates for the flat disk beyond the L2 restriction estimates.
In this paper, we give a new method to answer a recent conjecture proposed by Budaghyan, Calderini, Carlet, Davidova and Kaleyski about the equation xd+(x+1)d=b in Fq4, where n is a positive integer, ...q=2n and d=q3+q2+q−1. In particular, we directly determine the differential spectrum of this power function xd using a more simple and direct method compared with those in the literature.
Let q=2m. In this paper, we investigate permutation pentanomials over Fq2 of the form f(x)=xt+xr1(q−1)+t+xr2(q−1)+t+xr3(q−1)+t+xr4(q−1)+t with gcd(xr4+xr3+xr2+xr1+1,xt+xt−r1+xt−r2+xt−r3+xt−r4)=1. We ...transform the problem concerning permutation property of f(x) into demonstrating that the corresponding fractional polynomial permutes the unit circle U of Fq2 with order q+1 via a well-known lemma, and then into showing that there are no certain solution in Fq for some high-degree equations over Fq associated with the fractional polynomial. According to numerical data, we have found all such permutations with 4≤t<100,1≤ri≤t, i∈1,4. Several permutation polynomials are also investigated from the fractional polynomials permuting the unit circle U found in this paper.
Let $q$ be an odd prime power. We discuss possible definitions over $\FF_{q^2}$ (using the Hermitian form) of circles, unit segments and half-lines. If we use our unit segments to define the convex ...hulls of a set $S\subset \FF_{q^2}^n$ for $q\notin \{3,5,9\}$ we just get the $\FF_q$-affine span of $S$.
We present the open-source C++ library FireFly for the reconstruction of multivariate rational functions over finite fields. We discuss the involved algorithms and their implementation. As an ...application, we use FireFly in the context of integration-by-parts reductions and compare runtime and memory consumption to a fully algebraic approach with the program Kira.
Program title:FireFly
Program files doi:http://dx.doi.org/10.17632/nzgxdwwt8k.1
Licensing provisions: GNU General Public License 3
Programming language:C++
External routines/libraries used: GNU GMP1, FLINT2
Nature of problem: The interpolation of an unknown rational function, called black box, from only its evaluations can be used in many physical contexts where algebraic calculations fail due to memory and time restrictions.
Solution method: The black-box function is evaluated at different points over a finite field. These points are then used by interpolation algorithms3,4 to obtain the analytic form of the black-box function. The members of a finite field are promoted to Q using a rational reconstruction algorithm5,6.
Restrictions: The CPU time and the available RAM
References:
1 T. Granlund et al., The GNU Multiple Precision Arithmetic Library,https://gmplib.org/
2 W. Hart et al., FLINT: Fast Library for Number Theory, http://www.flintlib.org/
3 R. Zippel, J. Symb. Comp. 9 (1990) 375–403
4 A. Cuyt, W.-s. Lee, Theor. Comp. Sci. 412 (2011) 1445–1456
5 P.S. Wang, Proc. ACM Symp. Symbolic Algebraic Comp. 1981 (1981) 212–217
6 M. Monagan, Proc. Int. Symp. Symbolic Algebraic Comp. 2004 (2004) 243–249
Semi-regular sequences over F2 are sequences of homogeneous elements of the algebra B(n)=F2X1,...,Xn/(X12,...,Xn2), which have as few relations between them as possible. They were introduced in order ...to assess the complexity of Gröbner basis algorithms such as F4 and F5 for the solution of polynomial equations. Despite the experimental evidence that semi-regular sequences are common, it was unknown whether there existed semi-regular sequences for all n, except in extremely trivial situations. We prove some results on the existence and non-existence of semi-regular sequences. In particular, we show that if an element of degree d in B(n) is semi-regular, then we must have n≤3d. Also, we show that if d=2t and n=3d, then there exists a semi-regular element of degree d establishing that the bound is sharp for infinitely many n. Finally, we generalize the result of non-existence of semi-regular elements to the case of sequences of a fixed length m.
We present the main improvements and new features in version 2.0 of the open-source C++ library FireFly for the interpolation of rational functions. This includes algorithmic improvements, e.g. a ...hybrid algorithm for dense and sparse rational functions and an algorithm to identify and remove univariate factors. The new version is applied to a Feynman-integral reduction to showcase the runtime improvements achieved. Moreover, FireFly now supports parallelization with MPI and offers new tools like a parser for expressions or an executable for the insertion of replacement tables.
Program title:FireFly
CPC Library link to program files:https://doi.org/10.17632/nzgxdwwt8k.2
Code Ocean capsule:https://codeocean.com/capsule/4860843/tree/v1
Licensing provisions: GNU General Public License 3
Programming language:C++
Journal reference of previous version: J. Klappert, F. Lange, Comp. Phys. Commun. 247 (2020) 106951, , arXiv:1904.00009.
Does the new version supersede the previous version?: Yes
Reasons for the new version: Significant performance improvements and new features
Summary of revisions: We implemented new algorithms: The racing algorithm of Ref.1 for univariate polynomials, a dense and sparse hybrid algorithm for rational functions, and an algorithm to search for univariate factors which can be removed in the actual interpolation. In addition, we changed the interface to allow for an overhead reduction inspired by vectorization and implemented the parallelization with MPI. Moreover, we include some new tools, e.g. a parser for expressions and an executable for the insertion of replacement tables.
Nature of problem: The interpolation of an unknown rational function, called black box, from only its evaluations can be used in many physical contexts where algebraic calculations fail due to memory and runtime restrictions.
Solution method: The black-box function is evaluated at different points over a finite field. These points are then used by interpolation algorithms1-4 to obtain the analytic form of the function. The elements of a finite field are promoted to Q using rational reconstruction algorithms5,6.
Additional comments including restrictions and unusual features: For better performance, we advise to use FLINT7 for the finite-field arithmetics and an improved memory allocator like jemalloc8.
References:
1 E. Kaltofen, W.-s. Lee, J. Symb. Comp. 36 (2003) 365–400, .
2 M. Ben-Or, P. Tiwari, Proc. ACM Symp. Theory Comp. 20 (1988) 301–309, .
3 R. Zippel, J. Symb. Comp. 9 (1990) 375–403, .
4 A. Cuyt, W.-s. Lee, Theor. Comp. Sci. 412 (2011) 1445–1456, .
5 P.S. Wang, Proc. ACM Symp. Symbolic Algebraic Comp. 1981 (1981) 212–217, .
6 M. Monagan, Proc. Int. Symp. Symbolic Algebraic Comp. 2004 (2004) 243–249, .
7 W. Hart, et al., FLINT: Fast Library for Number Theory, http://www.flintlib.org/.
8 J. Evans, et al., jemalloc – memory allocator, http://jemalloc.net/.
Filling curves for Homma, Masaaki; Kim, Seon Jeong
Communications in algebra,
2023, Letnik:
51, Številka:
6
Journal Article
Recenzirano
We determine the minimal bi-degree(s) of an irreducible filling curve over
for
by constructing examples. It is
if
, and they are (4, 3) and (3, 4) if q = 2.
Let Fq denote the finite field with q elements. In this paper, based on the AGW criterion and determining the number of solutions to certain equations over the finite field Fp2m, several classes of ...permutation polynomials with given forms are proposed. Some of them are the permutation polynomials of the form (xpm−x+δ)s+L(x), where L(x) is a linearized polynomial. Others are the permutation polynomials of the form (xpm−x+δ)s1+(xpm−x+δ)s2+x.
PDF
