### Article

## Minimization of even conic functions on the two-dimensional integral lattice

Under consideration is the Successive Minima Problem for the 2-dimensional lattice

with respect to the order given by some conic function f.We propose an algorithm with complexity of

3.32*log_2(R)+O(1) calls to the comparison oracle of f, where R is the radius of the circular searching

area, while the best known lower oracle complexity bound is 3*log_2(R) + O(1).We give an efficient

criterion for checking that given vectors of a 2-dimensional lattice are successive minima and form

a basis for the lattice.Moreover, we show that the similar Successive Minima Problem for dimension

n can be solved by an algorithm with at most (O(n))^{2n}*log_2(R) calls to the comparison oracle. The

results of the article can be applied to searching successive minima with respect to arbitrary convex

functions defined by the comparison oracle.

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.

In this paper, we consider the class of quasiconvex functions and its proper subclass of conic functions. The integer minimization problem of these functions is considered, assuming that the optimized function is defined by the comparison oracle. We will show that there is no a polynomial algorithm on log R to optimize quasiconvex functions in the ball of radius R using only the comparison oracle. On the other hand, if the optimized function is conic, then we show that there is a polynomial on log R algorithm (the dimension is fixed). We also present an exponential on the dimension lower bound for the oracle complexity of the conic function integer optimization problem. Additionally, we give examples of known problems that can be polynomially reduced to the minimization problem of functions in our classes.

We consider the minimization problem for a symmetric quasiconvex function defined by an oracle on the set of integer points of a square. We formulate an optimality criterion for the solution, obtain a logarithmic lower bound for the complexity of the problem, and propose an algorithm for which the number of inquiries to the oracle is at most thrice the lower bound.

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.