A survey of Sylvester's problem and its generalizations

Summary LetP be a finite set of three or more noncollinear points in the plane. A line which contains two or more points ofP is called aconnecting line (determined byP), and we call a connecting lineordinary if it contains precisely two points ofP. Almost a century ago, Sylvester posed the disarmingly simple question:Must every set P determine at least one ordinary line? No solution was offered at that time and the problem seemed to have been forgotten. Forty years later it was independently rediscovered by Erdös, and solved by Gallai. In 1943 Erdös proposed the problem in the American Mathematical Monthly, still unaware that it had been asked fifty years earlier, and the following year Gallai's solution appeared in print. Since then there has appeared a substantial literature on the problem and its generalizations.In this survey we review, in the first two sections, Sylvester's problem and its generalization to higher dimension. Then we gather results about the connecting lines, that is, the lines containing two or more of the points. Following this we look at the generalization to finite collections of sets of points. Finally, the points will be colored and the search will be for monochromatic connecting lines.     

A strange pigeon-hole principle

Using Ramsey theory, we establish the following pigeon-hole type principle: From a large number of random variables (functions, vectors, etc.) one can always select two, X and Y, such that P(X < Y) 1/2. We apply the principle for a poset problem.     

The umbral calculus and orthogonal polynomials

We determine all orthogonal polynomials having Boas-Buck generating functions g(t)(xf(t)), where% MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacqqHOo% qwcaGGOaGaamiDaiaacMcacqGH9aqpruqqYLwySbacfaGaa8hiamaa% BeaaleaacaaIWaaabeaakiaadAeacaqGGaWaaSbaaSqaaiaabgdaae% qaaOGaaeikaiaadggacaGGSaGaa8hiaiaadshacaqGPaGaaeilaiaa% bccacaqGGaGaaeiiaiaadggacqGHGjsUcaaIWaGaaiilaiaa-bcacq% GHsislcaaIXaGaaiilaiaa-bcacqGHsislcaaIYaGaaiilaiablAci% ljaacUdaaeaacqqHOoqwcaGGOaGaamiDaiaacMcacqGH9aqpcaWFGa% WaaSraaSqaaiaaicdaaeqaaOGaamOraiaabccadaWgaaWcbaGaaeOm% aaqabaGccaGGOaWaaSqaaSqaaiaaigdaaeaacaaIZaaaaOGaaiilai% aa-bcadaWcbaWcbaGaaGOmaaqaaiaaiodaaaGccaGGSaGaa8hiaiaa% dshacaGGPaGaa8hiamaaBeaaleaacaaIWaaabeaakiaadAeacaqGGa% WaaSbaaSqaaiaabkdaaeqaaOGaaeikamaaleaaleaacaaIYaaabaGa% aG4maaaakiaacYcacaWFGaWaaSqaaSqaaiaaisdaaeaacaaIZaaaaO% Gaaiilaiaa-bcacaWG0bGaaiykaiaacYcacaWFGaWaaSraaSqaaiaa% icdaaeqaaOGaamOraiaabccadaWgaaWcbaGaaeOmaaqabaGccaGGOa% WaaSqaaSqaaiaaisdaaeaacaaIZaaaaOGaaiilaiaa-bcadaWcbaWc% baGaaGynaaqaaiaaiodaaaGccaGGSaGaa8hiaiaadshacaGGPaGaai% 4oaaqaaiabfI6azjaacIcacaWG0bGaaiykaiabg2da9iaa-bcadaWg% baWcbaGaaGimaaqabaGccaWGgbGaaeiiamaaBaaaleaacaqGZaaabe% aakiaacIcadaWcbaWcbaGaaGymaaqaaiaaisdaaaGccaGGSaGaa8hi% amaaleaaleaacaaIYaaabaGaaGinaaaakiaacYcacaWFGaWaaSqaaS% qaaiaaiodaaeaacaaI0aaaaOGaaiilaiaa-bcacaWG0bGaaiykaiaa% -bcadaWgbaWcbaGaaGimaaqabaGccaWGgbGaaeiiamaaBaaaleaaca% qGZaaabeaakiaabIcadaWcbaWcbaGaaGOmaaqaaiaaisdaaaGccaGG% SaGaa8hiamaaleaaleaacaaIZaaabaGaaGinaaaakiaacYcacaWFGa% WaaSqaaSqaaiaaiwdaaeaacaaI0aaaaOGaaiilaiaa-bcacaWG0bGa% aiykaiaacYcaaeaadaWgbaWcbaGaaGimaaqabaGccaWGgbGaaeiiam% aaBaaaleaacaqGZaaabeaakiaacIcadaWcbaWcbaGaaG4maaqaaiaa% isdaaaGccaGGSaGaa8hiamaaleaaleaacaaI1aaabaGaaGinaaaaki% aacYcacaWFGaWaaSqaaSqaaiaaiAdaaeaacaaI0aaaaOGaaiilaiaa% -bcacaWG0bGaaiykaiaacYcacaGGUaGaa8hiamaaBeaaleaacaaIWa% aabeaakiaadAeacaqGGaWaaSbaaSqaaiaabodaaeqaaOGaaeikamaa% leaaleaacaaI1aaabaGaaGinaaaakiaacYcacaWFGaWaaSqaaSqaai% aaiAdaaeaacaaI0aaaaOGaaiilaiaa-bcadaWcbaWcbaGaaG4naaqa% aiaaisdaaaGccaGGSaGaa8hiaiaadshacaGGPaGaaiOlaaaaaa!C1F3!\[\begin{gathered}\Psi (t) = {}_0F{\text{ }}_{\text{1}} {\text{(}}a, t{\text{), }}a \ne 0, - 1, - 2, \ldots ; \hfill \\\Psi (t) = {}_0F{\text{ }}_{\text{2}} (\tfrac{1}{3}, \tfrac{2}{3}, t) {}_0F{\text{ }}_{\text{2}} {\text{(}}\tfrac{2}{3}, \tfrac{4}{3}, t), {}_0F{\text{ }}_{\text{2}} (\tfrac{4}{3}, \tfrac{5}{3}, t); \hfill \\\Psi (t) = {}_0F{\text{ }}_{\text{3}} (\tfrac{1}{4}, \tfrac{2}{4}, \tfrac{3}{4}, t) {}_0F{\text{ }}_{\text{3}} {\text{(}}\tfrac{2}{4}, \tfrac{3}{4}, \tfrac{5}{4}, t), \hfill \\{}_0F{\text{ }}_{\text{3}} (\tfrac{3}{4}, \tfrac{5}{4}, \tfrac{6}{4}, t),. {}_0F{\text{ }}_{\text{3}} {\text{(}}\tfrac{5}{4}, \tfrac{6}{4}, \tfrac{7}{4}, t). \hfill \\\end{gathered}\]We also determine all Sheffer polynomials which are orthogonal on the unit circle. The formula for the product of polynomials of the Boas-Buck type is obtained.     

On a problem proposed by H. Braß concerning the remainder term in quadrature for convex functions

Summary We prove that the error inn-point Gaussian quadrature, with respect to the standard weight functionw1, is of best possible orderO(n ^–2) for every bounded convex function. This result solves an open problem proposed by H. Braß and published in the problem section of the proceedings of the 2. Conference on Numerical Integration held in 1981 at the Mathematisches Forschungsinstitut Oberwolfach (Hämmerlin 1982; Problem 2). Furthermore, we investigate this problem for positive quadrature rules and for general product quadrature. In particular, for the special class of Jacobian weight functionsw _, (x)=(1–x)(1+x), we show that the above result for Gaussian quadrature is not valid precisely ifw _, is unbounded.Dedicated to Prof. H. Braß on the occasion of his 55th birthday     

Density estimation and adaptive control of markov processes: Average and discounted criteria

We consider a class of discrete-time Markov control processes with Borel state and action spaces, and ^d i.i.d. disturbances with unknown distribution . Under mild semi-continuity and compactness conditions, and assuming that is absolutely continuous with respect to Lebesgue measure, we establish the existence of adaptive control policies which are (1) optimal for the average-reward criterion, and (2) asymptotically optimal in the discounted case. Our results are obtained by taking advantage of some well-known facts in the theory of density estimation. This approach allows us to avoid restrictive conditions on the state space and/or on the system's transition law imposed in recent works, and on the other hand, it clearly shows the way to other applications of nonparametric (density) estimation to adaptive control.Research partially supported by The Third World Academy of Sciences under Research Grant No. MP 898-152.     

On well-ordered mono-unary algebras

Given a linearly ordered set (A, _R ) and an R-monotone function f: AA, we give a necessary and sufficient condition on A, f, _R , involving generating sets and forbidden subalgebras, for _R to be a well-ordering.Partially supported by Hungarian National Foundation for Scientific Research Grant nr. 1813.     

Parallel and superfast algorithms for Hankel systems of equations

Summary Utilizing kernel structure properties a unified construction of Hankel matrix inversion algorithms is presented. Three types of algorithms are obtained: 1)O(n ²) complexity Levinson type, 2)O (n) parallel complexity Schur-type, and 3)O(n log² n) complexity asymptotically fast ones. All algorithms work without additional assumption (like strong nonsingularity).     

Perturbation theory for nonlinear feedback control systems and spencer-goldschmidt integrability of linear partial differential equations

This paper aims to develop the differential-geometric and Lie-theoretic foundations of perturbation theory for control systems, extending the classical methods of Poincaré from the differential equation-dynamical system level where they are traditionally considered, to the situation where the element of control is added. It will be guided by general geometric principles of the theory of differential systems, seeking approximate solutions of the feedback linearization equations for nonlinear affine control systems. In this study, certain algebraic problems of compatibility of prolonged differential systems are encountered. The methods developed by D. C. Spencer and H. Goldschmidt for studying over-determined systems of partial differential equations are needed. Work in the direction of applying theio theory is presented.Supported by grants from the Ames Research Center of NASA and the Applied Mathematics and Systems Research Programs of the National Science Foundation     

On a question of H. Kraljević

In this paper, assuming a certain set-theoretic hypothesis, a positive answer is given to a question of H. Kraljevi, namely it is shown that there exists a Lebesgue measurable subsetA of the real line such that the set {c R: A + cA contains an interval} is nonmeasurable. Here the setA + cA = {a + ca: a, a A}. Two other results about sets of the formA + cA are presented.     

The Binet-Pexider functional equation for rectangular matrices

IfK is a field of characteristic 0 then the following is shown. Iff, g, h: M _n (K) K are non-constant solutions of the Binet—Pexider functional equation