% Replace amsart by the documentclass for the target journal, e.g., proc-l tran-l.
\documentclass{amsart}
%\usepackage[left=0.6in,right=0.6in,top=0.69in,bottom=0.8in]{geometry}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{examples}[theorem]{Examples}
\newtheorem{xca}[theorem]{Exercise}
\newtheorem{qs}[theorem]{Question}
\newtheorem{con}[theorem]{Conjecture}
\newtheorem{pr}[theorem]{Problem}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\numberwithin{equation}{section}
% Absolute value notation
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\T}{\mathbb{T}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\J}{\mathbb{J}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\W}{\mathbb{V}}
\newcommand{\p}{\mathbb{P}}
\newcommand{\G}{G_{\delta}}
\newcommand{\g}{\widetilde{G}}
\newcommand{\C}{\mathbf{c}}
\newcommand{\s}{\mathbf{s}}
\newcommand{\h}{\text{Hom}(G,\T)}
\newcommand{\K}{\text{Hom}(K,\T)}
\newcommand{\B}{\mathcal{B}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\cal}{\mathcal}
\newcommand{\lqc}{\mathcal{LQC}}
\newcommand{\tr}{\triangleright}
\newcommand{\tl}{\triangleleft}
%\newcommand{\graf}{\text{graph}}
\newcommand{\graf}{\Gamma}
\newcommand{\cf}{\text{cf}}
\newcommand{\PP}{\mathcal{P}}
\def\cs{convex subsemigroup}
\def\NB{$\clubsuit\;\;$}
\def\NL{$\spadesuit \;\;$}
%}
\def\cont{\mathfrak c}
\def\SSS{\mathfrak S}
\def\L{\mathfrak L}
\def\SS_{{\mathfrak S}_{qc}}
\def\tq{\tau_{qc}}
%\frontmatter
% Blank box placeholder for figures (to avoid requiring any
% particular graphics capabilities for printing this document).
\newcommand{\blankbox}[2]{%
\parbox{\columnwidth}{\centering
% Set fboxsep to 0 so that the actual size of the box will match the
% given measurements more closely.
\setlength{\fboxsep}{0pt}%
\fbox{\raisebox{0pt}[#2]{\hspace{#1}}}%
}%
}
\begin{document}
\title{Computational aspects of a discrete extremum problem}
\author{Mikheil Nikoleishvili}
\address{N. Muskhelishvili Institute of Computational Mathematics of the Georgian Technical University, 0175 Tbilisi, Georgia}
\email{mikheil.nikoleishvili@gmail.com}
\author{Vaja Tarieladze}
\address{N. Muskhelishvili Institute of Computational Mathematics of the Georgian Technical University, 0175 Tbilisi, Georgia}
\email{v.tarieladze@gtu.ge}
% \thanks will become a 1st page footnote.
%\thanks{The first author was supported by grant MICINN: MTM2009-14409-C02-01.}
% General info
%\subjclass[2010]{Primary 46A03, 46A20; Secondary 46B10, 46B20}
\date{}
\dedicatory{ Dedicated to the memory of Alexander Semenovich Kronrod (1921--1986)}
%\dedicatory{}
\keywords{Cardinality, algorithm, complexity}
\begin{abstract}
Two problems related with a discrete extremum are discussed.
\end{abstract}
%\begin{abstract}
%\end{abstract}
\maketitle
\section{Introduction}
First several words about A.S. Kronrod. This name the second author discovered in September 2016 in Madrid during preparation of his talk about convergent series in topological groups. During this preparation he has arrived to the paper:
Kronrod A.,{\it On permutation of terms of numerical series}, Mat. Sbornik, 1946, 18(60), 237--280 (in Russian)
At the end of the paper it is written: received by editors 9.XII.1944.
After we have looked Wikipedia:
"Aleksandr (Alexander) Semenovich Kronrod (October 22, 1921 -- October 6, 1986) was a Soviet mathematician and computer scientist...
Kronrod was born in Moscow. In 1938 entered the Department of Mechanics and Mathematics at Moscow State University.
During World War II he was rejected for military service because at the time graduate level students were exempt. They did help to build trenches around Moscow, and when he returned, Kronrod reapplied and was accepted. He served twice, and was injured twice. He was awarded several medals, including Order of the Red Star and Order of the Patriotic War. The second injury in 1943 hospitalised him for a year and he was discharged from the army in 1944. This injury made him an invalid of sorts for life.
In his last undergraduate year, Kronrod studied with Nikolai Luzin the teacher of many of the Soviet Union's finest scientists.
Kronrod was married and about this time his son was born. During next four years he continued his studies at the University, simultaneously working at the Atomic Energy Kurchatov Institute.
When he defended thesis in 1949, his committee including M. V. Keldish, A. N. Kolmogorov and D. E. Men'shov bypassed the Candidate of Sciences degree and awarded him a Doctor of Sciences degree in the physical-mathematical sciences.
Then he chose to leave pure mathematics and pursue computational mathematics.
Kronod played an important role in building the first major Russian computer, Relay Computer RVM-1, though he liked to say his colleague N.I. Bessonov was the sole inventor. At the Moscow Institute for Theoretical and Experimental Physics (ITEF or ITEP) during 1950-1955 Kronod collaborated with physicists, among them Isaak Pomeranchuk and Lev Landau. For providing theoretical physics with numerical solutions he received the Stalin Prize and an Order of the Red Banner.
When the Communist Party reprimanded him in 1968 for cosigning a letter with many mathematicians in defense of the mathematician and logician Alexander Esenin-Volpin[(May 12, 1924 -- March 16, 2016)], a son of the poet Sergei Esenin, the physicists were able to oust him from ITEP. He was also fired from his professorship."
Let us add that the above-mentioned paper Kronrod wrote during his being in hospital.
Now about our talk.
In what follows,
$$
\mathbb N=\{1,2,\dots\},\,\,\mathbb Z_+=\{0,1,2,\dots\}\,.
$$
Let $L>1$,$n>1$ be natural numbers and let
$${\mathcal B}(L,n):=\left\{(x_1,\dots,x_n)\in \mathbb N^n: \sum_{i=1}^nx_i=L\right\}\,.$$
Moreover, we fix
$$(k_1,\dots,k_n)\in \mathbb Z_+ ^n\,\,\text{and}\,\,(s_1,\dots,s_n)\in \mathbb Z_+ ^n$$
and consider the set
$$ {\mathcal B}(L,n;k_1,\dots,k_n):=\left\{(x_1,\dots,x_n)\in {\mathcal B}(L,n): x_i>k_i,i=1,\dots,n\right\}\,.$$
Clearly,
\begin{equation}\label{22seq2}
{\mathcal B}(L,n;0,\dots,0)={\mathcal B}(L,n)\,.
\end{equation}
We assume that
\begin{equation}\label{22aug1}
L\ge \sum_{i=1}^nk_i+n\,\,.
\end{equation}
The condition (\ref{22aug1}) guarantees that
\begin{equation}\label{22seq3}
{\mathcal B}(L,n;k_1,\dots,k_n)\ne \emptyset\,\,.
\end{equation}
Since (\ref{22seq3}) is satisfied and the set ${\mathcal B}(L,n;k_1,\dots,k_n)$ is finite, the extremum
$$
b(L,n;k_1,\dots,k_n;s_1,\dots,s_n)
$$
of the set
$$
\left \{\prod_{i=1}^n(x_i+s_i): (x_1,\dots,x_n)\in {\mathcal B}(L,n;k_1,\dots,k_n) \right\}
$$
is well-defined by the equality:
$$ b(L,n;k_1,\dots,k_n;s_1,\dots,s_n)=\max\left \{\prod_{i=1}^n(x_i+s_i): (x_1,\dots,x_n)\in {\mathcal B}(L,n;k_1,\dots,k_n) \right\}\,.$$
\section{Problems}
The exact formula for $b(L,n;k_1,\dots,k_n;s_1,\dots,s_n)$ is known only in the following particular case:
\begin{proposition}\label{NT} {\em (\cite{NT})}
Let $k\ge 0$ and $L,n$ be natural numbers such that $L\ge n(k+1)$. Then
$$
b(L,n;k,\dots,k;0,\dots,0)=(1+q)^rq^{n-r}\,,
$$
where $q=[\frac{L}{n}]$ and $r=L-nq$.
\end{proposition}
In our communication we were going to discuss the following problems:
\begin{pr}\label{genprob1}
Find a formula (or find the sharp estimations from below and from above) for the cardinality (number of elements) of the set ${\mathcal B}(L,n;k_1,\dots,k_n)$.
\end{pr}
\begin{pr}\label{genprob2}
Find a general algorithm for calculating of $b(L,n;k_1,\dots,k_n;s_1,\dots,s_n)$ and estimate its computational complexity.
\end{pr}
%\section{Remarks about cardinalities}
In connection with Problem \ref{genprob1} from known results of Combinatorics we were able to derive the following assertion:
\begin{proposition}\label{NA}
Let $L\ge n>1$ be natural numbers. Then the set
$$
{\mathcal B}(L,n)
$$
contains
$$
C_{L-1}^{n-1}=\frac{(L-1)!}{(n-1)!(L-n)!}
$$
elements.
\end{proposition}
In general, Problem \ref{genprob1} remains open.
Problem \ref{genprob2} remains open as well.
{\bf Acknowledgements.} The authors were supported in part by Shota Rustaveli National Science Foundation
grant no. FR/539/5-100/13.
\bibliographystyle{amsplain}
\begin{thebibliography}{99}
\bibitem{NT}
Mikheil Nikoleishvili, Vaja Tarieladze, {\em About a problem of extremum}, Proceedings of the Fifth International Scientific-Practical Conference "Scientific Issues of the Modernity" at Sukhishvili Teaching University, Gori, Georgia, December, 13, 2014, pp. 401--403.
\end{thebibliography}
\end{document}