Dr Misha Rudnev

M.Sc.(Moscow Phys.& Engin.Inst.), Ph.D.(Cal.Tech.)

    • BS8 1UG

    If you made any changes in Pure these will be visible here soon.

    Personal profile

    Research interests

    Combinatorics. The name comes under many appellations, mine are Geometric, Arighmetic, and Additive combinatorics. Geometric combinatorics seeks first and foremost incidence bounds for finite arrangements of geometric obgects in space: points, lines, triangles, simplices, etc. An incidence is when two objects meet.  In other words, incidence theory seeks bounds for the number of solutions of (systems of) algebraic equations, whose variables are restricted to large finite sets. For instance, the famous Szemerédi-Trotter theorem claims that m lines and n points in the real plane have no more than C[ (mn)2/3 + m + n ] incidences, for some absolute constant (somewhat irrelevant, what one is after are the best posisble powers of and n). What if lines become circles? Only partial results are known. How about higher dimensions,  where lines may also be replaced by other affine geometric objects, say, planes or higher degree varieties? E.g., consider points and planes in three dimensions. Higher dimension allows for degeneracy -- all the planes and points may hang on a single line. Finally, what if the space is not over the reals but, say complex numbers or a finite field? 


    My best known contribution to incidence theory is the point-plane bound C[ mn1/2 + k n ] for the number of incidences between n<m points and m planes in three dimensions, where k is the maximum number of colinear points. Unlike the Szemerédi-Trotter theorem, the proof of the point-plane theorem has a purely algebraic nature and works over any field, not just reals (in positive characteristic there is an extra constraint n<p2). 

    A notable part of geometric combintorics finds ubiquity of finite point configurations in space. The classical example is the Erdös distance problem: what is the minimum number of distinct pairwise distances, determined by a set of points in Rd. It was solved in 2010 by Guth and Katz in dimension d=2, but is wide open in higher dimension. Similar questions can be asked about spaces over other fields. A stronger verison of the question -- what is the maximum number of realisaitons of a given distance in a set of  n points is wide open in the plane as well.  Moreover, seemingly looking questions (but deceptively, for they are not translation-invariant) about the minimum number of distinct dot products defined by a set of vectors in the plane are also open -- this one is one of my personal favourites. It was not until autumn 2021 that the ``threshold'' lower bound n2/3 that comes from the Szemerédi-Trotter theorem got finally beaten by my collaborators, building up on our recent work.

    Incidence theorems have been so far the main tool in Arithmetic combinatorics, which studies interaction between two ring operations: addition and multiplication. There the key open question, where I have done much research in the past years (and currently hold most of the best known partial "world record" results) is the Erdös-Szemerédi conjecture, roughly that a set of  scalars in a field (not too large in positive characteristic) defines "almost n2" (more precisely n2-o(1)hiding invariably present logarithmic terms) distinct pairwise sums or products.  Informally, any finite set of, say reals yields the nearly maximal number of sums or products. This is, of course, very much in contrast with infinite sets or finite fields of you take the whole field.

    This sum-product problem is a hard-to-crack diamond of modern mathematics. It originated in a 1983 paper by Erdös and Szemerédi about integers, hence in number theory. The question, with some restrictions, is valid in any algebraic structure, where one is allowed to add and multiply. In the early 2000s first qualitative sum-product bounds were obtained in the finite field setting,  leading to striking applications in cryptography and group theory. The sum-product phenomenon became a fountainhead of the whole theme  of growth throughout mathematics, computer science and complexity theory. I have done much research in it and hold many of the current "world records", but new ideas are badly needed for furhter progress.

    Additive combinatorics deals with only one operation, say addition in an Abelian group. Its large part focuses on studying the structure of sets, which are near extremal, for instance what does a finite but large set of  n elements in an Abelian group (say, integers, this connects to number theory) look like if the number of distinct pairwise sums it yields is in some sense comparable to n,  say, at most n1+c , for a tiny c. The central open problem in additive combinatorics is the so-called Polynomial-Freiman-Ruzsa conjecture, roughly that a set of integers yielding only Kn distinct pairwise sums, where K is tiny relative to n, say K~nc, has a large subset, which looks like an arithmtic progression, whose size is not much greater than N and the number of generators is ~log K.

     In the past 15 years there has aslo been plenty of reesearch apropos of the same question, that is structure of what may be regarded as approximate subgroups in non-commutative groups. Much of the modern state of the art was inspired by a 2005 paper by Helfgott. Today it is an advanced a fairly abstract theory covering much in the Chevalley group category. However, the "microscopic" mechanism, used by Helfgott for intrinsic growth in non-commutative groups by multiplicaiton, unless one is close to a subgroup, is he sum-product pehnomenon, for matrix multiplicaiton combines addition with multiplicaiton. 

    My recent line of research was partially to reverse the implication and use action of specific, fairly low rank groups, like SL_2 to study the sum-product phenomenon and attempt to prove new incidence results, aiming at, say beating, under more specific scenarios, the generally sharp Szemerédi-Trotter theorem.

    I led 3 PhD's in arithmetic/geometric combinatorics to their degrees and currently have 3 PhD students, two of which are finishing in 2021-22. I may take more, the theme of a PhD being a variation on the above research themes.

    Warning: these research-information.bris.ac.uk pages (i) do not list all PhD students one supervised, and (ii) list, along with actual supervisor, another academic, who was not involved in the mathematical aspects of the PhD, but whom the university regadrs as part of the supervision "team".