### Article

## A polynomial algorithm for minimizing discrete convic functions in fixed dimension

In Chirkov et al., (2019), classes of *conic* and *discrete conic* functions were introduced. In this paper we use the term *convic* instead *conic*. The class of convic functions properly includes the classes of convex functions, strictly quasiconvex functions and the class of quasiconvex polynomials. On the other hand, the class of convic functions is properly included in the class of quasiconvex functions. The discrete convic function is a discrete analogue of the convic function. In Chirkov et al., (2019), the lower bound 3^{n-1} log(R) for the number of calls to the comparison oracle needed to find the minimum of the discrete convic function defined on integer points of some n-dimensional ball with radius R was obtained. But the problem of the existence of a polynomial (in log(R) for fixed n) algorithm for minimizing such functions has remained open. In this paper, we answer positively the question of the existence of such an algorithm. Namely, we propose an algorithm for minimizing discrete convic functions that uses 2^{n^2 log(n)} log(R) calls to the comparison oracle and has 2^{n^2 log(n)} poly(log(R)) bit complexity.

Let f:R^n→R be a conic function and x_0∈R^n. In this note, we show that the shallow separation oracle for the set K={x∈R^n:f(x)≤f(x_0)} can be polynomially reduced to the comparison oracle of the function *f*. Combining these results with known results of D. Dadush et al., we give an algorithm with (O(n))^n*logR calls to the comparison oracle for checking the non-emptiness of the set K∩Z^n, where *K* is included to the Euclidean ball of a radius *R*. Additionally, we give a randomized algorithm with the expected oracle complexity (O(n))^n*logR for the problem to find an integral vector that minimizes values of *f* on an Euclidean ball of a radius *R*. It is known that the classes of convex, strictly quasiconvex functions, and quasiconvex polynomials are included into the class of conic functions. Since any system of conic functions can be represented by a single conic function, the last facts give us an opportunity to check the feasibility of any system of convex, strictly quasiconvex functions, and quasiconvex polynomials by an algorithm with (O(n))^n*logR calls to the comparison oracle of the functions. It is also possible to solve a constraint minimization problem with the considered classes of functions by a randomized algorithm with (O(n))^n*logR expected oracle calls.Let f:R^n→R be a conic function and x_0∈R^n. In this note, we show that the shallow separation oracle for the set K={x∈R^n:f(x)≤f(x_0)} can be polynomially reduced to the comparison oracle of the function *f*. Combining these results with known results of D. Dadush et al., we give an algorithm with (O(n))^n*logR calls to the comparison oracle for checking the non-emptiness of the set K∩Z^n, where *K* is included to the Euclidean ball of a radius *R*. Additionally, we give a randomized algorithm with the expected oracle complexity (O(n))^n*logR for the problem to find an integral vector that minimizes values of *f* on an Euclidean ball of a radius *R*. It is known that the classes of convex, strictly quasiconvex functions, and quasiconvex polynomials are included into the class of conic functions. Since any system of conic functions can be represented by a single conic function, the last facts give us an opportunity to check the feasibility of any system of convex, strictly quasiconvex functions, and quasiconvex polynomials by an algorithm with (O(n))^n*logR calls to the comparison oracle of the functions. It is also possible to solve a constraint minimization problem with the considered classes of functions by a randomized algorithm with (O(n))^n*logR expected oracle calls.

We consider certain spaces of functions on the circle, which naturally appear in harmonic analysis, and superposition operators on these spaces. We study the following question: which functions have the property that each their superposition with a homeomorphism of the circle belongs to a given space? We also study the multidimensional case.

We consider the spaces of functions on the m-dimensional torus, whose Fourier transform is p -summable. We obtain estimates for the norms of the exponential functions deformed by a C1 -smooth phase. The results generalize to the multidimensional case the one-dimensional results obtained by the author earlier in “Quantitative estimates in the Beurling—Helson theorem”, Sbornik: Mathematics, 201:12 (2010), 1811 – 1836.

We consider the spaces of function on the circle whose Fourier transform is p-summable. We obtain estimates for the norms of exponential functions deformed by a C1 -smooth phase.

Let k be a field of characteristic zero, let G be a connected reductive algebraic group over k and let g be its Lie algebra. Let k(G), respectively, k(g), be the field of k- rational functions on G, respectively, g. The conjugation action of G on itself induces the adjoint action of G on g. We investigate the question whether or not the field extensions k(G)/k(G)^G and k(g)/k(g)^G are purely transcendental. We show that the answer is the same for k(G)/k(G)^G and k(g)/k(g)^G, and reduce the problem to the case where G is simple. For simple groups we show that the answer is positive if G is split of type A_n or C_n, and negative for groups of other types, except possibly G_2. A key ingredient in the proof of the negative result is a recent formula for the unramified Brauer group of a homogeneous space with connected stabilizers. As a byproduct of our investigation we give an affirmative answer to a question of Grothendieck about the existence of a rational section of the categorical quotient morphism for the conjugating action of G on itself.

Let G be a connected semisimple algebraic group over an algebraically closed field k. In 1965 Steinberg proved that if G is simply connected, then in G there exists a closed irreducible cross-section of the set of closures of regular conjugacy classes. We prove that in arbitrary G such a cross-section exists if and only if the universal covering isogeny Ĝ → G is bijective; this answers Grothendieck's question cited in the epigraph. In particular, for char k = 0, the converse to Steinberg's theorem holds. The existence of a cross-section in G implies, at least for char k = 0, that the algebra k[G]G of class functions on G is generated by rk G elements. We describe, for arbitrary G, a minimal generating set of k[G]G and that of the representation ring of G and answer two Grothendieck's questions on constructing generating sets of k[G]G. We prove the existence of a rational (i.e., local) section of the quotient morphism for arbitrary G and the existence of a rational cross-section in G (for char k = 0, this has been proved earlier); this answers the other question cited in the epigraph. We also prove that the existence of a rational section is equivalent to the existence of a rational W-equivariant map T- - - >G/T where T is a maximal torus of G and W the Weyl group.