# Multimodal Deep Learning of Word-of-Mouth Text and Demographics to Predict
Customer Rating:
Handling Consumer Heterogeneity in Marketing

Junichiro Niimi<EMAIL_ADDRESS>Meijo University  RIKEN AIP

###### Abstract

In the marketing field, understanding consumer heterogeneity, which is the
internal or psychological difference among consumers that cannot be captured
by behavioral logs, has long been a critical challenge. However, a number of
consumers today usually post their evaluation on the specific product on the
online platform, which can be the valuable source of such unobservable
differences among consumers. Several previous studies have shown the validity
of the analysis on text modality, but on the other hand, such analyses may not
necessarily demonstrate sufficient predictive accuracy for text alone, as they
may not include information readily available from cross-sectional data, such
as consumer profile data. In addition, recent advances in machine learning
techniques, such as large-scale language models (LLMs) and multimodal learning
have made it possible to deal with the various kind of dataset simultaneously,
including textual data and the traditional cross-sectional data, and the joint
representations can be effectively obtained from multiple modalities.
Therefore, this study constructs a product evaluation model that takes into
account consumer heterogeneity by multimodal learning of online product
reviews and consumer profile information. We also compare multiple models
using different modalities or hyper-parameters to demonstrate the robustness
of multimodal learning in marketing analysis.

_Keywords_ Multimodal Learning $\cdot$ BERT $\cdot$ Customer Relationship
Management $\cdot$ Word-of-Mouth $\cdot$ LLM

##  1 Introduction

Deep learning is currently used in various fields. In the field such as image
recognition, it is already common to obtain features that affect the target
variable by the feature extraction of deep learning [1], and it is considered
one of the most powerful advantages of deep learning [2]. In the field of
customer relationship management (CRM) in marketing, it also has been widely
employed in various ways of prediction and demonstrated the validity of
utilizing deep learning, such as customer segmentation [3], customer lifetime
value (CLV) [4, 5], purchases (in the future or current session) [6, 7, 8],
churn [9, 10], and other tasks [11].

However, within the vast field of data science, a problematic factor, referred
as consumer heterogeneity, has been identified, particularly in marketing. In
marketing analysis, we combine a variety of behavioral log data; however, all
the data recorded in the behavioral logs are the results of behaviors. The
Differences in the psychological attributes among consumers that cause those
behaviors cannot be obseerved by such logs. Many previous studies have
highlighted the importance of considering heterogeneity [12, 13].

In terms of combining various data, multimodal learning [14, 15] has become
widely popular in machine learning applications in general. It combines and
learns different types of multiple data (i.e., modality), for example, audio
and its corresponding text, in a state close to the original data. This method
allows modeling that considers the relationships between modalities. However,
in the marketing field, analysis using such a variety of data is generally
conducted by variablizing each data into a single dataset [16].

This paper is organized as follows. The previous studies are reviewed in
Section 2, and the methodology (proposed model and used data) is shown in
Section 3. An overview of the analysis is described in Section 4. The results
of the analysis are presented in Section 5. Finally, we present the discussion
and conclusions in Section 6.

##  2 Related Work

###  2.1 Text Analysis in Marketing

Natural Language Processing (NLP) techniques have been proposed for analyzing
text modalities using deep learning. Among them, bidirectional encoder
representations from transformers (BERT) [17] and their extensions [18, 19]
are some of the most popular methods because of their wide applicability,
which is not limited to NLP tasks, such as machine translation and question
answering. For pre-training, it has learned a contextual language
representations using large text corpus; therefore, it can be further applied
to various downstream tasks through fine-tuning. Many models have already
undergone pretraining with extensive data, enabling effective analysis with
relatively small datasets. In recent years, an extension of BERT into multiple
languages, known as multilingual BERT (mBERT), has emerged, and several models
for the Japanese version, which is the focus of this study, have also been
proposed (e.g., BERT models trained by Cyber Agent [20] and Tohoku NLP Group
[21]). Before the advent of BERT, vectorization methods such as word2vec [22]
and doc2vec [23] had been used to map sentences to feature vectors. Compared
with techniques that produce a single- word embedding representation, the
advantage of BERT is that it is context-wise, which means that it produces a
representation based on other terms in the sentence [17, 24].

For the actual use of these methods in marketing, especially regarding word-
of-mouth texts, this study [24] predicts user review (that is, sentiment) for
smartphone games using review texts collected from the Google Play Store,
which compare several techniques to obtain word representations, including RNN
[25], CNN [26], LSTM [27], BERT, mBERT, DistilBERT [18], and RoBERTa [19]. In
addition, a study [28] adopted BERT to predict customers’ ratings of hotels in
seven criteria (e.g., overall ratings, value, and service) simultaneously,
using online review texts for the recommender system. They indicated that BERT
could predict a more accurate rating by considering the context of a review
text. Another study regarding social media marketing [29] adopts BERT to
capture the social media engagements and comments of influencers of eight
categories on Instagram. Thus, several studies have used BERT to map word-of-
mouth documents to feature maps to predict customer evaluations.

In addition, while BERT has two different scale: Base (approx. 110 million
parameters) and Large (approx. 340 million parameters), the extent to which
such scales of BERT affect the result of the analysis for relatively small
text data is yet to be clarified, particularly in non-English models111The
results are comparable between the model scales since both BERT models of Base
and Large are designed to handle the same number of input tokens..

###  2.2 Multimodal Learning in Marketing

Multimodal learning involves learning representations from multiple modalities
such as images, videos, audio, and text. A combination of these enables the
construction of a robust learner based on the relationships among modalities
that cannot be obtained by learning a single modality [15]. There are a
variety of applications, including the integration of information from
multiple sources and interconversion between modalities, applied to a wide
range of academic fields such as medicine, human-computer interaction,
biometrics, and remote sensing [30]. In contrast to this rise in multimodal
learning, research on multimodal learning in the marketing field is relatively
scarce. One possible reason is that marketing data analysis involves a mixture
of various data in different formats, such as server logs, ID-POS, GPS, survey
responses, and customer information. Although analyses combining various
datasets are widely practiced, they are typically conducted by variablizing
multiple data and merging them into a single set for analysis 222The
information loss occurring in the process of converting behavioral log into
cross-sectional data may lead to a decrease in the accuracy of marketing
analysis using deep learning. In other words, the manually variablized
features cannot be sufficient statistics for the task on their own..

However, there are a few notable instances, such as studies that construct a
multimodal deep learning model to predict consumer loyalty with the
source–target attention mechanism [31], which datasets with different
dimensionality are input simultaneously; however, by using bidirectional LSTM,
the time-series data is converted to two-dimensional and unified to a single
representation with cross-sectional data by feature fusion333Notably, in both
studies, data fusion is conducted twice in one network structure: source-
target attention and feature fusion..

###  2.3 Consumer Heterogeneity in Marketing

Both the studies mentioned above highlight that it is possible to enhance
discriminative power by considering demographic variables as a context
affecting actual behavior. In the CRM context, the problem of consumer
heterogeneity has long been highlighted, where even consumers who perform same
behavior have unobservable differences [12], such as demographic and
psychographic differences. In general, this kind of difference is unobservable
in behavioral logs such as ID–POS data. Several studies have attempted to
capture such differences using statistical modeling, such as structural
equation modeling (SEM) and Bayesian mixture models [32, 33]. When it comes to
the evaluation of the results addressed in this study, even among customers
who have the same rating (number of stars), the reasons for the rating must
differ; however, this difference cannot be observed in the cross-sectional
data. In recent years, with the availability of a variety of large-scale data,
document data such as word-of-mouth on online platforms have been used in the
aforementioned studies as an important source for understanding consumer
preferences [34].

Thus, several studies have utilized BERT and text data to make predictions
that account for consumer heterogeneity. In general, the review text has more
or less amount of reason why they evaluate the venue in such rating. In other
words, the data, although it is behavioral log, can be the important source of
understanding consumer heterogeneity. Therefore, this study utilize product
review as a means to capture consumer heterogeneity to predict with better
performance.

On the other hand, relying sorely on the feature extraction of machine
learning is not advisable because domain knowledge is not incorporated into
the analysis. In fact, several studies have shown that in multimodal learning,
the combination of extracted features and handcrafted variables achieves the
best prediction accuracy [1, 16]. Therefore, this study constructs a
multimodal deep learning model that combines the review text with handcrafted
user profile variables to achieve a robust and precise model.

##  3 Proposed Model

Based on previous studies of multimodal learning using time series and cross-
sectional data [17], we present a conceptual model of multimodal deep learning
that integrates three smaller neural network components, referred to as
subnetworks or subnets. In this study, they are called text-specific
subnetworks (X1-subnet), cross-sectional-data-specific subnetworks
(X2-subnet), and output subnetworks (output-subnet). The construction of each
subnet is described in the following subsections.

Figure 1: Model Architecture

###  3.1 Text-Specific Subnetworks (X1-subnet)

First, we describe the structure of the X1-subnet, which specializes in
processing text data. The purpose of this subnet is to map word-of-mouth texts
(whose lengths differ among users) onto a two-dimensional single-feature map.
The actual component included two layers: a tokenization layer and a BERT
layer. In this study, BERT was used to obtain embedded representations of text
data; therefore, the X1-subnet (tokenizer and BERT layers) is freezed
throughout the actual training process, which means that the parameters of the
subnet are held fixed in the pre-trained state.

The text data contains the review of $N$ users and is processed with tokenizer
into fixed-length of ($N,~{}len_{max}$) tensor ($len_{max}$ represents the
maximum number of tokens of the text among $N$ sets of data). After processing
in the BERT layer with batch size $n$, we obtained the feature map as the
pooler output of BERT as the ($n,len_{max}$) tensor.444The maximum length of
the text $len_{max}\leq 512$ since it cannot be exceeded the maximum number of
tokens that BERT can deal with.

###  3.2 Cross-Sectional-Data-Specific Subnetworks (X2-subnet)

Next, we describe the structure of the X2-subnet handling two-dimensional
cross-sectional data. This subnet consists of a typical deep neural network
with feed-forward layers (FFLs). An input layer for the X2-subnet receives a
2-dimensional tensor ($n,~{}J_{in}$), with batch size $n$ and $J_{in}$
variables in the cross-sectional data. After processing, ($n,~{}J_{out}$)
feature map is obtained as the output.

###  3.3 Output Subnetworks (output-subnet)

Textual and cross-sectional data, processed in parallel in each dedicated
subnet are sent to the output subnet. In this subnet, both the feature maps,
stemming from X1 and X2, are unified as a joint representation by feature
fusion layer555However, a more rigorous call of feature fusion in this study
should be ”intermediate fusion” [30]., and the obtained feature map would be
($n,~{}len_{max}+J_{out}$) tensor. After the feature fusion, the joint
representation is processed through one or more FFLs, and finally
classification is conducted with Softmax layer. All the FFLs throughout the
model employed a hyperbolic tangent function ($tanh$) for layer activation.

##  4 Analysis

###  4.1 Dataset

To conduct this analysis, we randomly selected one product from the women’s
cosmetics market. The target product had to be well-recognized in Japan and
already out of production. We collected data from 1040 participants online.
The actual data contains three kinds of modalities: rating for the product
(7-point Likert scale), word-of-mouth texts for the product, and demographic
information 666Since the cosmetic we focus on is a product intended for use by
females, the survey was limited to females who purchased the products
themselves.. Finally, the sample size is 1532 (i.e., $N=1532$).

Next, we process the survey text in the general way of preprocessing in NLP.
The text contained line breaks, pictographs, emoticons, and other characters
that were not appropriate for analysis. Therefore, in the preprocessing stage,
these elements were replaced with periods only when they were placed at the
end of the sentence; otherwise, the elements were removed. Subsequently, all
successive punctuation periods are merged into a single period. Consequently,
the maximum length of the text data was set as $len_{max}=200$.

###  4.2 Model Evaluation

This study adopts a simple binary classification for the task, similar to
previous studies [24]. User ratings were dichotomized into two classes based
on the rating scale. Six and seven stars were classified as $Loyalty=1$
(loyalty is high) and $Loyalty=0$ (loyalty is not high), respectively. The
obtained dataset was divided into a training set (75%) and a test set (25%).
The model performance was evaluated using both training and test accuracies
and the number of epochs to converge.

This study aims to validate several key points to compare the models. First,
to validate the usefulness of multimodal learning in marketing, we construct
three basic models according to their modalities: X1-modal, X2-modal, and
multimodal. This comparison allowed for the verification of changes in
prediction accuracy by combining multiple modalities. Especially in marketing
analysis, review texts can be a valuable source for comprehending consumer
heterogeneity in user ratings.

Next, we examined the change in prediction accuracy using multiple pre-trained
models within BERT. Regarding the Japanese language model, several models of
different scales (that is, numbers of parameters), different training
datasets, and tokenization methods (in particular, with regard to Japanese
models, some are trained on a word-by-word basis, whereas others are trained
on a character-by-character basis) have already been proposed, and the extent
to which the prediction accuracy differs depending on the use of these models
is yet to be clarified. Nowadays, we can easily switch the pre-trained model
in BERT by changing one line of the code, which makes it easy to compare the
accuracies of different pre-trained models. As it has already been shown in
the literatures [24, 28, 29] that models using BERT-like architectures achieve
higher accuracy compared to those using Collaborative Filtering, LSTM, CNN,
and other benchmark models, this study sticks to comparing among multiple
models using BERT.

The model settings are shown in Table 1. In the case where several candidates
are shown in the setting, we utilize a grid search to explore the settings
that maximize the test accuracy. For example, we compared the prediction
accuracy among the four pre-trained models in BERT (bert base/large in
word/char) and among three optimizers (Adaptive Moment Estimation, Adam [35],
Adamax [35], and Nesterov-accelerated Adaptive Moment Estimation, Nadam [36]).

The training process was conducted with a maximum of 200 epochs and 64 batch
sizes. Early Stopping [37] was employed with a patience of 50 epochs, which
terminates the training if no improvement in the accuracy of the validation
data was observed within 50 epochs.

Table 1: Model Settings

Parameters | Candidates
---|---
Model Parameters
| Number of Epochs | 200 (with Early-Stopping in 50 Epochs)
| Batchsize ($n$) | 64
| Optimizer | {Adam, Adamax, Nadam}
| Loss Function | Binary Cross-entropy
X1-subnet
| Structure | mBERT (Japanese)
| Model | {bert-base-japanese-v3,
|  | bert-base-japanese-char-v3,
|  | bert-large-japanese-v2,
|  | bert-large-japanese-char-v2}
X2-subnet
| Number of Hidden Layers | 2
| Number of Neurons in the Layer | 10
| Activation Function | tanh
output-subnet
| Number of Hidden Layers | 2
| Number of Neurons in the Layer | 10
| Activation Function | tanh

  * Note. tanh stands for hyperbolic tangent function.

##  5 Results

The best models for each modality are listed in Table 2. First, in both the
training and test results, the prediction accuracy improved the most with
multimodal learning. Although these results do not allow us to evaluate
whether multimodal learning immediately improves the prediction accuracy,
multimodal learning with the bert-base-japanese-v3 model shows the highest
prediction accuracy for the test data, which indicates that the extension to
multimodal learning alone does not improve the prediction accuracy. For
multimodal learning, we need to carefully consider factors such as the task to
be solved with the multimodal model, the relationship between the modalities,
and the quality of the data, because several previous studies have shown that
the prediction accuracy in multimodal learning can be influenced by such
factors [38].

Second, in the comparison of four pre-trained models, note that upgrading to
the BERT Large model did not always lead to a significant improvement in
accuracy. Regarding the scale of the model, there is a tendency for an
increase in the number of epochs required for model training with bert-large-
japanese-v2, and the X1-modality has reached 190 epochs. This result might
indicate the potential for further improvement with an increase in the number
of epochs; however, large model is not always necessary because other models
have shown higher prediction accuracy in fewer epochs.

Table 2: Result I (Accuracy in Train and Test Data)

| Train | Test | Epochs
---|---|---|---
BERT Model / Modality | Both | X1 | X2 | Both | X1 | X2 | Both | X1 | X2
cl-tohoku/bert-base-japanese-v3 | 0.705 | 0.708 | - | 0.711 | 0.703 | - |  36 |  38 | -
cl-tohoku/bert-base-japanese-char-v3 | 0.683 | 0.686 | - | 0.690 | 0.678 | - |  41 |  42 | -
cl-tohoku/bert-large-japanese-v2 | 0.712 | 0.698 | - | 0.695 | 0.699 | - |  95 | 190 | -
cl-tohoku/bert-large-japanese-char-v2 | 0.681 | 0.658 | - | 0.690 | 0.703 | - |  58 |  18 | -
None | - | - | 0.555 | - | - | 0.623 | - | - |  29

  * Note. Numbers in bold represent the best accuracy in training and testing and the best epochs.

Table 3: Result II (Group Average)

Optimizer |  Train |  Test | Epochs |  | Modality |  Train |  Test | Epochs
---|---|---|---|---|---|---|---|---
Adam | 0.646 | 0.659 | 58.4 |  | Both | 0.681 | 0.683 | 70.2
Adamax | 0.627 | 0.651 | 61.7 |  | X1 | 0.685 | 0.681 | 58.9
Nadam | 0.646 | 0.662 | 46.2 |  | X2 | 0.546 | 0.604 | 35.5

  * Note. Numbers in bold represent the best accuracy in training and testing and the best epochs.

In addition, a comparison of the mean accuracies among certain conditions is
listed in Table 3. In terms of the optimizer, although the training accuracy
is almost the same between Adam and Nadam, the latter is better in terms of
both test accuracy and the best epoch, which means that, on average, Nadam
achieved a higher generalization performance in a shorter time777Note that the
time required for training one epoch did not differ significantly among
optimizers.. In terms of modality, the X1-modal shows high accuracy, as listed
in Table 2, for the training process; however, multimodal learning, on
average, still shows the highest accuracy for the test data. This result
suggests that, on average, multimodal learning improves generalization
performance. As expected, the accuracy of the analysis using only X2-modal
remains low for both training and testing, although the model converged early.

##  6 Conclusions

This study attempts to construct a multimodal deep learning model that
predicts the user ratings of a product using both review text and user profile
data simultaneously to account for consumer heterogeneity. First, as academic
implications, even when both review and demographic data are relatively small,
both the best model and the average score by modality, the prediction accuracy
is the best when they are combined, which indicates that multimodal learning
that accounts for consumer heterogeneity allows analysis with high robustness
and generalizability. Second, it can be shown that, at least when dealing with
relatively short sentences such as those used in this study ($len_{max}=200$),
a larger BERT model does not necessarily contribute to an improvement in
prediction accuracy. This implies that, particularly in small datasets like
those used in this study, converting sentences into word embeddings with BERT
is important while the scale of the BERT model is not necessarily critical.
Next, the conceptual model presented in this study, as a way to extend review
data with cross-sectional data or as a way to extend cross-sectional data with
review data, has a potential to be extended to various prediction models in
marketing analysis with higher prediction accuracy, compared to conventional
methods.

Finally, owing to the constraints of data collection, this study relies on
consumer ratings as a proxy for behavioral loyalty and predicts whether it is
high or not using the proposed model. However, this methodology can be
extended to purchase prediction models by incorporating data that include
purchase history and more demographics. A few models in previous studies [31]
fused modalities twice within a model through the use of attention mechanisms
and feature fusion, which aims to enhance prediction accuracy and robustness.
Moreover, regarding the actual analysis, further improvements in accuracy can
be expected by adopting techniques such as dropout [39]. In addition, although
the multimodal learning model developed in this study, which utilizes actual
review texts as a source of information for understanding consumer
heterogeneity, is based on the assumption that consumer heterogeneity is
embedded in the review texts, the actual causal relationships need to be
carefully examined for the presence of potential endogeneity between the
variables.

## Acknowledgements

All computations in this study were conducted using RAIDEN, which is a
computational infrastructure hosted by RIKEN AIP. We would like to express our
gratitude to all the members of AIP who maintain the system.

## References

  * [1] Loris Nanni, Stefano Ghidoni, and Sheryl Brahnam.  Handcrafted vs. non-handcrafted features for computer vision classification.  Pattern Recognition, 71:158–172, 2017.
  * [2] Yoshua Bengio.  Deep learning of representations: Looking forward.  In International Conference on Statistical Language and Speech Processing, pages 1–37. Springer, 2013.
  * [3] Licheng Zhao, Yi Zuo, and Katsutoshi Yada.  Sequential classification of customer behavior based on sequence-to-sequence learning with gated-attention neural networks.  Advances in Data Analysis and Classification, pages 1–33, 2022\.
  * [4] Rafet Sifa, Julian Runge, Christian Bauckhage, and Daniel Klapper.  Customer lifetime value prediction in non-contractual freemium settings: Chasing high-value users using deep neural networks and smote.  2018\.
  * [5] Pei Pei Chen, Anna Guitart, Ana Fernández del Río, and Africa Periánez.  Customer lifetime value in video games using deep learning and parametric models.  In 2018 IEEE international conference on big data (big data), pages 2134–2140. IEEE, 2018.
  * [6] Jan Valendin, Thomas Reutterer, Michael Platzer, and Klaudius Kalcher.  Customer base analysis with recurrent neural networks.  International Journal of Research in Marketing, 39(4):988–1018, 2022.
  * [7] Arthur Toth, Louis Tan, Giuseppe Di Fabbrizio, and Ankur Datta.  Predicting shopping behavior with mixture of rnns.  In eCOM@ SIGIR, 2017.
  * [8] Long Guo, Lifeng Hua, Rongfei Jia, Binqiang Zhao, Xiaobo Wang, and Bin Cui.  Buying or browsing?: Predicting real-time purchasing intent using attention-based deep network with multiple behavior.  In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1984–1992, 2019.
  * [9] C Gary Mena, Arno De Caigny, Kristof Coussement, Koen W De Bock, and Stefan Lessmann.  Churn prediction with sequential data and deep neural networks. a comparative analysis.  arXiv preprint arXiv:1909.11114, 2019.
  * [10] Philip Spanoudes and Thomson Nguyen.  Deep learning in customer churn prediction: unsupervised feature learning on abstract company independent feature vectors.  arXiv preprint arXiv:1703.03869, 2017.
  * [11] Mainak Sarkar and Arnaud De Bruyn.  Lstm response models for direct marketing analytics: Replacing feature engineering with deep learning.  Journal of Interactive Marketing, 53(1):80–95, 2021.
  * [12] Peter E Rossi, Robert E McCulloch, and Greg M Allenby.  The value of purchase history data in target marketing.  Marketing Science, 15(4):321–340, 1996.
  * [13] Werner J Reinartz and Vita Kumar.  The impact of customer relationship characteristics on profitable lifetime duration.  Journal of marketing, 67(1):77–99, 2003.
  * [14] Nitish Srivastava and Russ R Salakhutdinov.  Multimodal learning with deep boltzmann machines.  Advances in neural information processing systems, 25, 2012.
  * [15] Jiquan Ngiam, Aditya Khosla, Mingyu Kim, Juhan Nam, Honglak Lee, and Andrew Y Ng.  Multimodal deep learning.  In ICML, 2011.
  * [16] Junichiro Niimi and Takahiro Hoshino.  Predicting purchases with using the variety of customer behaviors -analysis of the purchase history and the browsing history by deep learning-.  Transactions of the Japanese Society for Artificial Intelligence, 32(2):B–G63_1–9, 2017.
  * [17] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [18] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf.  DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter.  arXiv, 2019.
  * [19] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  arXiv preprint arXiv:1907.11692, 2019.
  * [20] Alex Andonian, Quentin Anthony, Stella Biderman, Sid Black, Preetham Gali, Leo Gao, Eric Hallahan, Josh Levy-Kramer, Connor Leahy, Lucas Nestler, Kip Parker, Michael Pieler, Shivanshu Purohit, Tri Songz, Wang Phil, and Samuel Weinbach.  GPT-NeoX: Large Scale Autoregressive Language Modeling in PyTorch, 8 2021.
  * [21] Tohoku NLP Group.  cl-tohoku/bert-japanese (github: https://github.com/cl-tohoku/bert-japanese), 2023.
  * [22] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  arXiv preprint arXiv:1301.3781, 2013.
  * [23] Quoc Le and Tomas Mikolov.  Distributed representations of sentences and documents.  In International conference on machine learning, pages 1188–1196. PMLR, 2014.
  * [24] Zeynep Hilal Kilimci.  Prediction of user loyalty in mobile applications using deep contextualized word representations.  Journal of Information and Telecommunication, 6(1):43–62, 2022\.
  * [25] David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams.  Learning representations by back-propagating errors.  nature, 323(6088):533–536, 1986.
  * [26] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [27] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural computation, 9(8):1735–1780, 1997.
  * [28] Yuanyuan Zhuang and Jaekyeong Kim.  A bert-based multi-criteria recommender system for hotel promotion management.  Sustainability, 13(14):8039, 2021.
  * [29] Seungbae Kim, Xiusi Chen, Jyun-Yu Jiang, Jinyoung Han, and Wei Wang.  Evaluating audience loyalty and authenticity in influencer marketing via multi-task multi-relational learning.  In Proceedings of the International AAAI Conference on Web and Social Media, volume 15, pages 278–289, 2021.
  * [30] Dhanesh Ramachandram and Graham W Taylor.  Deep multimodal learning: A survey on recent advances and trends.  IEEE signal processing magazine, 34(6):96–108, 2017.
  * [31] Maher Ala’raj, Maysam F Abbod, and Munir Majdalawieh.  Modelling customers credit card behaviour using bidirectional lstm neural networks.  Journal of Big Data, 8(1):1–27, 2021.
  * [32] Carsten Hahn, Michael D Johnson, Andreas Herrmann, and Frank Huber.  Capturing customer heterogeneity using a finite mixture pls approach.  Schmalenbach Business Review, 54:243–269, 2002.
  * [33] Thomas Otter, Regina Tüchler, and Sylvia Frühwirth-Schnatter.  Capturing consumer heterogeneity in metric conjoint analysis using bayesian mixture models.  International Journal of Research in Marketing, 21(3):285–297, 2004\.
  * [34] Silvana Aciar, Debbie Zhang, Simeon Simoff, and John Debenham.  Recommender system based on consumer product reviews.  In 2006 IEEE/WIC/ACM International Conference on Web Intelligence (WI 2006 Main Conference Proceedings)(WI’06), pages 719–723. IEEE, 2006.
  * [35] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [36] Timothy Dozat.  Incorporating nesterov momentum into adam.  2016\.
  * [37] Lutz Prechelt.  Early stopping-but when?  In Neural Networks: Tricks of the trade, pages 55–69. Springer, 1998.
  * [38] Douwe Kiela and Léon Bottou.  Learning image embeddings using convolutional neural networks for improved multi-modal semantics.  In Proceedings of the 2014 Conference on empirical methods in natural language processing (EMNLP), pages 36–45, 2014.
  * [39] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: a simple way to prevent neural networks from overfitting.  The journal of machine learning research, 15(1):1929–1958, 2014\.


# Erdős’ minimum overlap problem

Ethan Patrick White

###### Abstract

We obtain a substantially improved lower bound for the minimum overlap problem
asked by Erdős. Our approach uses elementary Fourier analysis to translate the
problem to a convex optimization program.

††The author is grateful for support from the Killam Trusts, NSERC, and
UBC.††2020 _Mathematics Subject Classification:_ 05A17, 42A16, 90C90

##  1 Introduction

In 1955 Erdős posed the following problem [1]. Let $n$ be a positive integer
and $A,B\subset[2n]$ be a partition of $[2n]$ such that $|A|=|B|=n$. For any
such partition and integer $-2n<k<2n$, define $M_{k}$ to be the number of
solutions $(a,b)\in A\times B$ to $a-b=k$. Estimate the size of the function

$M(n)=\min_{A\cup B=[2n]}\max_{-2n<k<2n}M_{k},$

where the minimum is taken over all partitions of $[2n]$ into equal-sized
sets. Erdős proved that $M(n)>n/4$, a result that can be obtained by the
following averaging argument. The sum over all $-2n<k<2n$ of $|M_{k}|$ is
exactly $|A\times B|=n^{2}$, and so the average value of $|M_{k}|$ exceeds
$n/4$. On the other hand, we can take $A$ to be $[n/2,3n/2]$ giving the upper
bound $M(n)\leq n/2$. The minimum overlap problem appears in Richard Guy’s
renown book, _Unsolved Problems in Number Theory_. See his book for a brief
survey of the progress made by many authors on improved estimates of $M(n)$
[2].

Haugland proved that the limit

$\mu:=\lim_{n\to\infty}\frac{M(n)}{n},$

exists [3]. We will refer to $\mu$ as the _minimum overlap constant_. Prior to
this work, the best estimates of $\mu$ were

$0.35639395869\approx\sqrt{4-\sqrt{15}}\leq\mu\leq 0.3809268534330870.$

The lower bound above is due to Moser [7], and the upper bound is due to
Haugland [4]. Moser and Murdeshwar were the first to study the following
function analogue of Erdős’ original problem. For all measurable functions
$f\colon[-1,1]\to[0,1]$ define the complementary function
$g\colon[-1,1]\to[0,1]$ such that $f(x)+g(x)=1$ for all $x\in[-1,1]$. Estimate
the value of

$\inf_{f}\sup_{x\in[-2,2]}\int_{-1}^{1}f(t)g(x+t)\ dt,$ (1.1)

where the minimum is taken over all measurable $f\colon[-1,1]\to[0,1]$
satisfying $\int_{-1}^{1}f(x)\ dx=1$. A key step in Haugland’s method is a
theorem of Swinnerton-Dyer proving that (1.1) is in fact also $\mu$, see [3]
for the proof. It will be easiest for us to work with (1.1) as our definition
of $\mu$. In this work we obtain a significant improvement on the lower bound
of $\mu$, using elementary Fourier analysis combined with convex programming.

######  Theorem 1.

The minimum overlap constant $\mu$ is lower bounded by $0.379005$.

The bound in Theorem 1 can certainly be improved with more computation time
for our convex program. The upper and lower bounds for $\mu$ now differ by
$0.5\%$.

##  2 Outline

Throughout this work, $f(x),g(x),M(x)$ will always denote measurable functions
satisfying the relationships

$f\colon[-1,1]\to[0,1]\text{ such that }\int_{-1}^{1}f(x)\ dx=1;$
$g\colon[-1,1]\to[0,1]\text{ such that }f(x)+g(x)=1\text{ for all
}x\in[-1,1];$ $M\colon[-2,2]\to[0,1]\text{ such that
}M(x)=\int_{-1}^{1}f(t)g(x+t)\ dt.$ (2.1)

The minimum overlap problem is to determine the largest $\mu$ such that
$\|M\|_{\infty}\geq\mu$ for all functions $M$ satisfying (2.1). Lower bounds
on $\mu$ can be obtained by observing properties held by $M(x)$. For example,
a first simple property held by $M(x)$ is

$\int_{-2}^{2}M(x)\ dx=\int_{-2}^{2}\int_{-1}^{1}f(t)g(x+t)\
dtdx=\int_{-1}^{1}f(t)\int_{-2}^{2}g(x+t)\ dxdt=1.$ (2.2)

Therefore the average value of $M(x)$ is at least 0.25 and so $\mu\geq 0.25$.
The discrete version of this argument was already mentioned in the
introduction. A second property held by $M(x)$, and the key insight in Moser
and Murdeshwar’s method [7], [8] is that

$\int_{-2}^{2}(x-E(M))^{2}M(x)\ dx\leq 2/3,\quad\text{where}\quad
E(M)=\int_{-2}^{2}xM(x)\ dx,$ (2.3)

is the expected value of $M(x)$. In other words, the variance of $M(x)$ is
upper bounded by $2/3$. The variance of a function is minimized when as much
mass as possible is centred at its mean. Therefore the variance of $M(x)$ is
at least the variance of

$\tilde{M}(x)=\begin{cases}\mu&\text{if }-\frac{1}{2\mu}\leq
x\leq\frac{1}{2\mu}\\\ 0&\text{otherwise.}\end{cases}$

The variance of $\tilde{M}$ is $1/(12\mu^{2})$. Since $1/(12\mu^{2})\leq 2/3$
we have $\mu\geq 1/\sqrt{8}$.

The key idea behind our improvement is that Fourier analysis can be used to
construct an infinite number of new properties satisfied by $M(x)$. The most
important new property we find and use is that all even cosine Fourier
coefficients of $M(x)$ are nonpositive, i.e.

$\int_{-2}^{2}\cos(\pi kx)M(x)\ dx\leq 0,\quad\text{for all }k\geq 1.$ (2.4)

The way we take advantage of these new properties is by constructing a linear
program where the variables represent the average value of $M(x)$ over small
intervals. With this programming technique we can transfer (2.2), (2.3), and
(2.4) into constraints of a linear program. This short program is the subject
of Section 4. Under the assumption that an optimal $f(x)$ is even, the output
of this program proves $\mu\geq 0.375$.

In order to prove our larger lower bound in Theorem 1 and remove the
assumption that an optimal $f(x)$ is even, we use a more complicated convex
program. This is the subject of Section 5. The new properties of $f(x),M(x)$
pairs we find are derived in Section 3. These new properties become the
constraints used in the linear program of Section 4 and the convex program of
Section 5. In Section 5 we discuss the data collected from the convex program
and prove Theorem 1.

##  3 Set up

In this section we derive properties about $f,g,M$ that will form key
constraints in the programs used in later sections.

###  3.1 Properties from Fourier analysis

The properties derived in this subsection relate to the Fourier coefficients
of $f,g,M$. We first consider $f,g,M$ as functions on $[-2,2]$. In the case of
$f$ and $g$ we define $f(x)=g(x)=0$ for $x\not\in[-1,1]$. Their Fourier
transforms are defined for all $k\in\mathbb{Z}$ and given by

$\hat{f}(k)=\frac{1}{4}\int_{-2}^{2}e^{-\frac{\pi i}{2}kx}f(x)\
dx,\quad\hat{g}(k)=\frac{1}{4}\int_{-2}^{2}e^{-\frac{\pi i}{2}kx}f(x)\
dx,\quad\hat{M}(k)=\frac{1}{4}\int_{-2}^{2}e^{-\frac{\pi i}{2}kx}M(x)\ dx.$

######  Lemma 2.

For all $f,M$ satisfying (2.1) and $k\in\mathbb{Z}\setminus\\{0\\}$ we have

$\hat{M}(k)=\frac{4}{k\pi}\sin\left(k\pi/2\right)\overline{\hat{f}(k)}-4|\hat{f}(k)|^{2},$

where $\hat{f},\hat{M}$ denote the Fourier transforms of $f,M$ on $[-2,2]$.

###### Proof.

Denote the indicator function of $[-1,1]$ by $\mathbf{1}_{[-1,1]}$. We have

$\displaystyle\hat{M}(k)$ $\displaystyle=\frac{1}{4}\int_{-2}^{2}e^{-\frac{\pi
i}{2}kx}M(x)\ dx=\frac{1}{4}\int_{-2}^{2}e^{-\frac{\pi
i}{2}kx}\int_{-1}^{1}f(t)g(x+t)\ dt\ dx$
$\displaystyle=\frac{1}{4}\int_{-1}^{1}e^{\frac{\pi
i}{2}kt}f(t)\int_{-2}^{2}e^{-\frac{\pi i}{2}k(x+t)}g(x+t)\ dx\
dt=4\overline{\hat{f}(k)}\hat{g}(k)$
$\displaystyle=4\overline{\hat{f}(k)}\left(\hat{\mathbf{1}}_{[-1,1]}(k)-\hat{f}(k)\right).$

Combining the above with

$\hat{\mathbf{1}}_{[-1,1]}(k)=\frac{1}{4}\int_{-1}^{1}e^{-\frac{\pi
i}{2}kx}=\frac{1}{k\pi}\sin\left(k\pi/2\right),$

gives the claimed identity. ∎

It will be advantageous to work with real Fourier coefficients in our programs
of the later sections. We will derive identities relating the coefficients of
the sine-cosine Fourier series of $f(x)$ as a function on $[-1,1]$ with the
sine-cosine Fourier series of $f(x)$ and $M(x)$ as functions on $[-2,2]$. Let

$f(x)=\frac{1}{2}+\sum_{k=1}^{\infty}c_{k}\cos(k\pi
x)+\sum_{k=1}^{\infty}d_{k}\sin(k\pi x),$ (3.1)

be the sine-cosine Fourier series of $f(x)$ on $[-1,1]$. It will be
notationally helpful to put $c_{0}=1/2$. Also let

$f(x)=\frac{1}{4}+\sum_{k=1}^{\infty}a_{k}\cos(k\pi
x/2)+\sum_{k=1}^{\infty}b_{k}\sin(k\pi x/2),\quad\text{and}$
$M(x)=\frac{1}{4}+\sum_{k=1}^{\infty}A_{k}\cos(k\pi
x/2)+\sum_{k=1}^{\infty}B_{k}\sin(k\pi x/2)$ (3.2)

be the sine-cosine Fourier series of $f$ and $M$ on $[-2,2]$.

######  Lemma 3.

Let $f,M$ be as in (2.1) and their sine-cosine Fourier series be as in (3.1)
and (3.2). Then for all $m\geq 1$:

$a_{m}=\begin{cases}\frac{1}{2}c_{m/2}&\text{if }m\text{ is even}\\\
\frac{2m\sin(\pi
m/2)}{\pi}\sum_{k=0}^{\infty}\frac{(-1)^{k}}{m^{2}-4k^{2}}c_{k}&\text{if
}m\text{ is odd.}\end{cases}$ (3.3)

$b_{m}=\begin{cases}\frac{1}{2}d_{m/2}&\text{if }m\text{ is even}\\\
\frac{4\sin(\pi
m/2)}{\pi}\sum_{k=1}^{\infty}\frac{k(-1)^{k}}{m^{2}-4k^{2}}d_{k}&\text{if
}m\text{ is odd.}\end{cases}$ (3.4)

$A_{m}=\frac{4\sin\left(m\pi/2\right)}{m\pi}a_{m}-2(a_{m}^{2}+b_{m}^{2}),\text{
and in particular }A_{2m}\leq 0.$ (3.5)
$B_{m}=-\frac{4}{m\pi}\sin\left(m\pi/2\right)b_{m},\text{ and in particular
}B_{2m}=0.$ (3.6)

###### Proof.

Note that the denominators in equations (3.3) and (3.4) are never zero since
$m$ is an odd integer while $4k^{2}$ is even. The convergence of the two
infinite sums in (3.3) and (3.4) is implied by Lemma 4 below. To derive (3.3)
we use the following integral identities, valid for all $m\geq 1$.

$\int_{-1}^{1}\cos(\pi mx/2)\cos(\pi kx)\ dx=\begin{cases}1&\text{ if }m\text{
is even and }k=m/2\\\ 0&\text{ if }m\text{ is even and }k\neq m/2\\\
\frac{4m(-1)^{k}\sin(\pi m/2)}{\pi m^{2}-4\pi k^{2}}&\text{ if }m\text{ is
odd. }\end{cases}$

We also have the identity $\int_{-1}^{1}\cos(\pi mx/2)\sin(\pi kx)\ dx=0$ for
all $k,m\in\mathbb{Z}$. Combining these identities with

$a_{m}=\frac{1}{2}\int_{-1}^{1}\cos(\pi mx/2)f(x)\ dx,$

gives (3.3). Similarly, we have for all $m\geq 1$ the integral identity

$\int_{-1}^{1}\sin(\pi mx/2)\sin(\pi kx)\ dx=\begin{cases}1&\text{ if }m\text{
is even and }k=m/2\\\ 0&\text{ if }m\text{ is even and }k\neq m/2\\\
\frac{8k(-1)^{k}\sin(\pi m/2)}{\pi m^{2}-4\pi k^{2}}&\text{ if }m\text{ is
odd. }\end{cases}$

For all $k,m\in\mathbb{Z}$ we have $\int_{-1}^{1}\sin(\pi mx/2)\cos(\pi kx)\
dx=0$. Combining this and the above with

$b_{m}=\frac{1}{2}\int_{-1}^{1}\sin(\pi mx/2)f(x)\ dx,$

gives (3.4). To derive (3.5) and (3.6) we need relations between the
exponential Fourier coefficients and the sine-cosine Fourier coefficients.
These are

$2\hat{f}(m)=a_{m}-ib_{m},\quad 2\hat{f}(-m)=a_{m}+ib_{m},\quad
A_{m}=\hat{M}(m)+\hat{M}(-m),\quad B_{m}=i(\hat{M}(m)-\hat{M}(-m)).$

By Lemma 2 and the above identities we have

$\displaystyle A_{m}$ $\displaystyle=\hat{M}(m)+\hat{M}(-m)$
$\displaystyle=\frac{4}{m\pi}\sin(k\pi/2)\left(\overline{\hat{f}(m)}+\overline{\hat{f}(-m)}\right)-4\left(|\hat{f}(m)|^{2}+|\hat{f}(-m)|^{2}\right)$
$\displaystyle=\frac{4\sin\left(m\pi/2\right)}{m\pi}a_{m}-2(a_{m}^{2}+b_{m}^{2}).$

Equation (3.6) is derived similarly. ∎

The identities in Lemma 3 will be used to construct constraints in our later
programs. In order to work with the infinite sums of (3.3) and (3.4) we will
bound the tails of the series using Parseval’s identity and the Cauchy-Schwarz
inequality.

######  Lemma 4.

Let $T$ be a positive integer, and $f(x)$ be as in (2.1) with sine-cosine
Fourier series (3.1). Then for all integers $1\leq m<2T$ we have

$\left|\frac{2m}{\pi}\sum_{k=T+1}^{\infty}\frac{(-1)^{k}\sin(\pi
m/2)}{m^{2}-4k^{2}}c_{k}\right|\leq\frac{1}{4-m^{2}/T^{2}}\cdot\frac{2m}{\pi\sqrt{6T^{3}}},$

and

$\left|\frac{4}{\pi}\sum_{k=T+1}^{\infty}\frac{k(-1)^{k}\sin(\pi
m/2)}{m^{2}-4k^{2}}d_{k}\right|\leq\frac{1}{4-m^{2}/T^{2}}\cdot\frac{4}{\pi\sqrt{2T}}.$

###### Proof.

Let $\hat{f}$ denote the Fourier transform of $f(x)$ on $[-1,1]$ defined for
$k\in\mathbb{Z}$ by

$\hat{f}(k)=\frac{1}{2}\int_{-1}^{1}e^{-i\pi kx}f(x)\ dx.$

For $k\geq 1$ we have $\hat{f}(k)=(c_{k}-id_{k})/2$, and
$f(-k)=(c_{k}+id_{k})/2$. By Parseval’s identity and the fact $\hat{f}(0)=1/2$
we obtain

$1\geq\int_{-1}^{1}f^{2}(x)\
dx=2\sum_{k\in\mathbb{Z}}|\hat{f}(k)|^{2}=\frac{1}{2}+\sum_{k=1}^{\infty}(c_{k}^{2}+d_{k}^{2}).$
(3.7)

Fix an integer $1\leq m<2T$. By the triangle inequality

$\left|\sum_{k=T+1}^{\infty}\frac{(-1)^{k}\sin(\pi
m/2)}{m^{2}-4k^{2}}c_{k}\right|\leq\sum_{k=T+1}^{\infty}\frac{|c_{k}|}{4k^{2}-m^{2}}\leq\frac{1}{4-m^{2}/T^{2}}\sum_{k=T+1}^{\infty}\frac{|c_{k}|}{k^{2}}.$

By the Cauchy-Schwarz inequality and (3.7)

$\left(\sum_{k=T+1}^{\infty}\frac{|c_{k}|}{k^{2}}\right)^{2}\leq\left(\sum_{k=T+1}^{\infty}c_{k}^{2}\right)\left(\sum_{k=T+1}^{\infty}\frac{1}{k^{4}}\right)\leq\frac{1}{2}\int_{T}^{\infty}\frac{1}{x^{4}}\
dx=\frac{1}{6T^{3}}.$

Combining the two last above lines gives the first tail estimate. We proceed
similarly for the second. By the triangle inequality

$\left|\sum_{k=T+1}^{\infty}\frac{k(-1)^{k}\sin(\pi
m/2)}{m^{2}-4k^{2}}d_{k}\right|\leq\sum_{k=T+1}^{\infty}\frac{k|d_{k}|}{4k^{2}-m^{2}}\leq\frac{1}{4-m^{2}/T^{2}}\sum_{k=T+1}^{\infty}\frac{|d_{k}|}{k}.$

By the Cauchy-Schwarz inequality and (3.7)

$\left(\sum_{k=T+1}^{\infty}\frac{|d_{k}|}{k}\right)^{2}\leq\left(\sum_{k=T+1}^{\infty}d_{k}^{2}\right)\left(\sum_{k=T+1}^{\infty}\frac{1}{k^{2}}\right)\leq\frac{1}{2}\int_{T}^{\infty}\frac{1}{x^{2}}\
dx=\frac{1}{2T}.$

Combining the two last above lines gives the second tail estimate.

∎

###  3.2 Properties using average values of $M(x)$ on small intervals

In our convex program, the Fourier coefficients $c_{k},d_{k}$ described above
will be variables. The other main type of variable will represent average
values of $M(x)$ on small intervals. Throughout the remainder of this work $N$
will denote a large positive integer and we’ll also define $L=2/N$. For each
$1\leq j\leq N$ define

$w_{j}=\frac{1}{L}\int_{(j-1)L}^{jL}M(x)\ dx\quad\text{and}\quad
v_{j}=\frac{1}{L}\int_{-jL}^{-(j-1)L}M(x)\ dx.$

Note that

$1=\int_{-2}^{2}M(x)\ dx=\sum_{j=1}^{N}\int_{(j-1)L}^{jL}(M(x)+M(-x))\
dx=L\sum_{j=1}^{N}(w_{j}+v_{j}).$ (3.8)

In this subsection we will estimate the Fourier coefficients, the second
moment, and the mean of $M(x)$ using the average values
$\\{w_{j},v_{j}\\}_{j=1}^{N}$. Let $R$ be a positive integer. For all $1\leq
j\leq N$ and $1\leq m\leq R$, let $\alpha^{+}_{j,m}$ and $\alpha^{-}_{j,m}$ be
upper and lower bounds of $\cos(\pi mx/2)$ on the interval $[(j-1)L,jL]$, i.e.

$\alpha_{j,m}^{+}\geq\max_{(j-1)L\leq x\leq jL}\cos(\pi
mx/2)\quad\text{and}\quad\alpha_{j,m}^{-}\leq\min_{(j-1)L\leq x\leq
jL}\cos(\pi mx/2).$ (3.9)

Similarly, define $\beta^{+}_{j,m}$ and $\beta^{-}_{j,m}$ to be upper and
lower bounds of $\sin(\pi mx/2)$ on the same intervals:

$\beta_{j,m}^{+}\geq\max_{(j-1)L\leq x\leq jL}\sin(\pi
mx/2)\quad\text{and}\quad\beta_{j,m}^{-}\leq\min_{(j-1)L\leq x\leq jL}\sin(\pi
mx/2).$ (3.10)

Next, we use the arrays $\\{\alpha^{+}_{j,m},\alpha^{-}_{j,m}\\}$ and
$\\{\beta^{+}_{j,m},\beta^{-}_{j,m}\\}$ to give estimates on the Fourier
coefficients of $M(x)$.

######  Lemma 5.

For all $1\leq m\leq R$

$\frac{L}{2}\sum_{j=1}^{N}\alpha_{j,m}^{-}(w_{j}+v_{j})\leq
A_{m}\leq\frac{L}{2}\sum_{j=1}^{N}\alpha_{j,m}^{+}(w_{j}+v_{j}).$
$\frac{L}{2}\sum_{j=1}^{N}(\beta_{j,m}^{-}w_{j}-\beta_{j,m}^{+}v_{j})\leq
B_{m}\leq\frac{L}{2}\sum_{j=1}^{N}(\beta_{j,m}^{+}w_{j}-\beta_{j,m}^{-}v_{j}).$

###### Proof.

Let $m\geq 1$. We can break the integrals defining $A_{r}$ into a sum of
integrals on the small intervals:

$\displaystyle A_{m}$ $\displaystyle=\frac{1}{2}\int_{-2}^{2}\cos(\pi
mx/2)M(x)\ dx$ $\displaystyle=\frac{1}{2}\int_{-2}^{2}\cos(\pi
mx/2)(M(x)+M(-x))\ dx$
$\displaystyle=\frac{1}{2}\sum_{j=1}^{N}\int_{(j-1)L}^{jL}\cos(\pi
mx/2)(M(x)+M(-x))\ dx.$ (3.11)

By definition of $\alpha_{j,m}^{+}$, for all $1\leq j\leq N$ we have

$\int_{(j-1)L}^{jL}\cos(\pi mx/2)(M(x)+M(-x))\
dx\leq\alpha_{j,m}^{+}\int_{(j-1)L}^{jL}(M(x)+M(-x))\
dx=L\alpha_{j,m}^{+}(w_{j}+v_{j}).$

Substituting the above back into (3.11) gives the stated upper bound on
$A_{m}$. The lower bound is similar. We can also break $B_{m}$ into the
following sum of integrals.

$B_{m}=\frac{1}{2}\sum_{j=1}^{N}\int_{(j-1)L}^{jL}\sin(\pi mx/2)(M(x)-M(-x))\
dx.$

For all $1\leq j\leq N$ and $(j-1)L\leq x\leq jL$ we have

$\beta_{j,m}^{-}M(x)-\beta_{j,m}^{+}M(-x)\leq\sin(\pi
mx/2)(M(x)-M(-x))\leq\beta_{j,m}^{+}M(x)-\beta_{j,m}^{-}M(-x).$

Substituting these estimates into the above expression for $B_{m}$ gives the
stated upper and lower bounds on $B_{m}$.

∎

Define the mean of $f,g,M$ as follows.

$E(f)=\int_{-1}^{1}xf(x)\ dx,\quad E(g)=\int_{-1}^{1}xg(x)\ dx,\quad
E(M)=\int_{-2}^{2}xM(x)\ dx.$

We will use a bound on the second moment of $M(x)$. A similar bound is used in
the work of Moser and Murdeshwar [8].

######  Lemma 6.

For all $M$ as in (2.1) we have

$\int_{-2}^{2}x^{2}M(x)\ dx=\frac{2}{3}+\frac{1}{2}E(M)^{2}.$

###### Proof.

By changing the order of integration, we obtain

$E(M)=\int_{-1}^{1}f(t)\int_{-2}^{2}(x+t)g(x+t)\
dxdt-\int_{-1}^{1}tf(t)\int_{-2}^{2}g(x+t)\ dxdt=E(g)-E(f).$

A similar change of order gives

$\displaystyle\int_{-2}^{2}x^{2}M(x)\ dx$
$\displaystyle=\int_{-1}^{1}f(t)\int_{-2}^{2}x^{2}g(x+t)\ dxdt$
$\displaystyle=\int_{-1}^{1}f(t)\int_{-2}^{2}((x+t)^{2}-2t(x+t)+t^{2})g(x+t)\
dxdt$ $\displaystyle=\int_{-1}^{1}x^{2}g(x)\
dx-2E(f)E(g)+\int_{-1}^{1}t^{2}f(t)\ dt$
$\displaystyle=\int_{-1}^{1}x^{2}(g(x)+f(x))\
dx-2E(f)E(g)=\frac{2}{3}-2E(f)E(g).$

A simple calculation shows that $E(f)=-E(g)$ and so $E(f)=-E(M)/2$.
Substituting these identities into the above gives the claimed result.

∎

Now we give an estimation of the mean and second moment of $M(x)$ using
$\\{w_{j},v_{j}\\}_{j=1}^{N}$.

######  Lemma 7.

Let $h_{1}\leq h_{2}$ be real numbers such that $h_{1}\leq E(M)\leq h_{2}$.
Then

$h_{1}\leq L^{2}\sum_{j=1}^{N}(jw_{j}-(j-1)v_{j})\quad\text{and}\quad
L^{2}\sum_{j=1}^{N}((j-1)w_{j}-jv_{j})\leq h_{2},$

and

$2/3+h_{1}^{2}/2\leq L^{3}\sum_{j=1}^{N}j^{2}(w_{j}+v_{j})\quad\text{and}\quad
L^{3}\sum_{j=1}^{N}(j-1)^{2}(w_{j}+v_{j})\leq 2/3+h_{2}^{2}/2.$

###### Proof.

Once again we break down the appropriate integral into a sum of integrals.

$E(M)=\int_{-2}^{2}xM(x)\ dx=\sum_{j=1}^{N}\int_{(j-1)L}^{jL}x(M(x)-M(-x))\
dx.$

For all $1\leq j\leq N$ we can upper and lower bound the summand above.

$(j-1)L^{2}w_{j}-jL^{2}v_{j}\leq\int_{(j-1)L}^{jL}x(M(x)-M(-x))\ dx\leq
jL^{2}w_{j}-(j-1)L^{2}v_{j}.$

Substituting this back into the above expression for $E(M)$ and then applying
$h_{1}\leq E(M)\leq h_{2}$ gives the upper and lower bounds stated. Secondly
for the second moment:

$\int_{-2}^{2}x^{2}M(x)\ dx=\sum_{j=1}^{N}\int_{(j-1)L}^{jL}x^{2}(M(x)+M(-x))\
dx.$

For all $1\leq j\leq N$ we can again upper and lower bound the summand above.

$(j-1)^{2}L^{3}(w_{j}+v_{j})\leq\int_{(j-1)L}^{jL}x^{2}(M(x)-M(-x))\ dx\leq
j^{2}L^{3}(w_{j}+v_{j}).$

Substituting this estimate into the above expression for the second moment
gives

$L^{3}\sum_{j=1}^{N}j^{2}(w_{j}+v_{j})\leq\int_{-2}^{2}x^{2}M(x)\ dx\leq
L^{3}\sum_{j=1}^{N}(j-1)^{2}(w_{j}+v_{j}).$

Applying Lemma 6 gives the two required inequalities.

∎

##  4 Simplified linear program

In this section we describe a simplified linear program version of our
technique that is meant to convey the main idea of the more complex convex
program in the following section. In this section we will derive a lower bound
on $\|M\|_{\infty}$ under the additional assumption that $M$ is even, i.e.
$M(x)=M(-x)$. The input of the linear program will be positive integers $N,R$
and $L=2/N$. We will also explicitly choose values for the array
$\\{\alpha_{j,m}^{-}\\}$ defined in (3.9). Set

$\alpha_{j,m}^{-}=\cos(\pi mL(j-1/2)/2)-\pi mL/4,\quad 1\leq j\leq N,1\leq
m\leq 2R.$

Note that the above choice satisfies the definition (3.9) since the derivative
of $\cos(\pi mx/2)$ is bounded in absolute value by $\pi m/2$. Our linear
program is the following.

$\displaystyle\textsc{Input: }N,R,L=2/N$ Variables:
$\displaystyle\Omega,w_{1},\ldots,w_{N}$ Minimize: $\displaystyle\Omega$
Subject to: $\displaystyle 0\leq w_{j}\leq\Omega;\quad 1\leq j\leq N,$ (4.1)
$\displaystyle\sum_{j=1}^{N}w_{j}=N/4,$ (4.2)
$\displaystyle\sum_{j=1}^{N}\alpha_{j,2m}^{-}w_{j}\leq 0;\quad 1\leq m\leq R,$
(4.3) $\displaystyle L^{3}\sum_{j=1}^{N}(j-1)^{2}w_{j}\leq 1/3.$ (4.4)

######  Proposition 8.

Let $N,R$ be arbitrary positive integers, and $M(x)$ be as in (2.1) with the
additional property that $M(x)$ is even. If $\Omega^{*}$ is the optimum of the
above program, then $\|M\|_{\infty}\geq\Omega^{*}$.

###### Proof.

Our strategy is to show that any even $M(x)$ gives a feasible assignment of
variables such that $\Omega\leq\|M\|_{\infty}$. Let $M(x)$ be even, fix
positive integers $N,R$. Put $\Omega=\|M\|_{\infty}$ and
$w_{j}=\frac{1}{L}\int_{(j-1)L}^{jL}M(x)\ dx$. Clearly this assignment of
variables satisfies the constraints in (4.1). Since $M(x)$ is even, we have

$\frac{1}{2}=\int_{0}^{2}M(x)\ dx=\sum_{j=1}^{N}\int_{(j-1)L}^{jL}M(x)\
dx=L\sum_{j=1}^{N}w_{j},$

satisfying constraint (4.2). By Lemma 5 and (3.5) of Lemma 3, for all $1\leq
m\leq R$ we have

$\frac{L}{2}\sum_{j=1}^{N}\alpha_{j,2m}^{-}w_{j}\leq A_{2m}\leq 0,$

satisfying constraint (4.3). Lastly, from Lemma 6 we have

$L^{3}\sum_{j=1}^{N}(j-1)^{2}w_{j}\leq\int_{0}^{2}x^{2}M(x)\ dx=1/3,$

satisfying constraint (4.4).

∎

The optimum of this linear program increases with $N$ and $R$. A linear
program with hundreds of constraints and variables can be solved exactly. For
our linear program, it is best to choose $N\geq 2000$. At this scale of
variables and constraints, exact-solvers are computationally slow, but
numerical solvers are still very fast. The disadvantage of numerical solvers
is that additional post-processing steps must be taken to ensure the reported
results are correct. Our strategy will be to find a feasible point in the dual
program, which will give a lower bound on the minimum to the primal problem.
To guarantee our dual solution is truly feasible, we will check that all
inequalities that define the dual space are strictly satisfied by a margin
that exceeds the worst-case-scenario for floating-point rounding errors.

Choosing $N=80000$ and $R=20$ and running the dual program in CPLEX returns a
feasible point in the dual space with objective 0.375169005340707. We have
verified that all constraints are satisfied by a margin exceeding the worst-
case floating point error accumulation. Therefore $\|M\|_{\infty}\geq 0.375$
for all even $M$. By increasing $N$ and $R$ this bound can be improved a
little, but it seems that the limit of this approach is less than $0.3755$. In
the next section we will introduce nonlinear constraints that will give a
substantial improvement.

##  5 Full convex program

In this section we give and discuss our main program that will be used to
prove Theorem 1. The convex program we will use includes the ideas of the
previous linear program, but will also add constraints coming from (3.6) which
will be important since we no longer assume $M(x)$ is even. We will also add
quadratic constraints coming from (3.5). There will be several inputs to our
convex program. Let $N,R$ denote positive integers, their role will be roughly
the same as in the simplified linear program. A positive integer $T$ will also
be an input, its role is as in Lemma 4 and determines when we truncate certain
infinite sums. Finally our last inputs will be real numbers
$h_{1}<h_{2},p_{1}<p_{2},q_{1}<q_{2}$. These inputs will act as bounds on the
mean of $M(x)$, first cosine, and first sine Fourier coefficient of $f(x)$. We
will also explicitly choose values for the arrays
$\\{\alpha_{j,m}^{-},\alpha_{j,m}^{+}\\}$ and
$\\{\beta_{j,m}^{-},\beta_{j,m}^{+}\\}$ defined in (3.9) and (3.10). Set

$\alpha_{j,m}^{-}=\cos(\pi mL(j-1/2)/2)-\pi
mL/4,\quad\alpha_{j,m}^{+}=\cos(\pi mL(j-1/2)/2)+\pi mL/4,$
$\beta_{j,m}^{-}=\sin(\pi mL(j-1/2)/2)-\pi mL/4,\quad\beta_{j,m}^{+}=\sin(\pi
mL(j-1/2)/2)+\pi mL/4,$

for all $1\leq j\leq N$ and $1\leq m\leq 2R$. As above, these choices satisfy
the definitions of (3.9) and (3.10) since the derivatives of $\cos(\pi mx/2)$
and $\sin(\pi mx/2)$ are bounded by $\pi m/2$. Our full convex program is the
following.

Input: $\displaystyle N,L=2/N,T,R,h_{1},h_{2},p_{1},p_{2},q_{1},q_{2}$
Variables:
$\displaystyle\Omega,\\{w_{j},v_{j}\\}_{j=1}^{N},\\{c_{k},d_{k}\\}_{k=1}^{T},\\{\epsilon_{2m-1},\delta_{2m-1}\\}_{j=1}^{R},$
Variable expressions: $\displaystyle\text{For }1\leq m\leq 2R:$ $\displaystyle
a_{m}=\begin{cases}\frac{1}{2}c_{m/2}&\text{if }m\text{ is even}\\\
\epsilon_{m}+\frac{2m\sin(\pi
m/2)}{\pi}\left(\frac{1}{2m^{2}}+\sum_{k=1}^{T}\frac{(-1)^{k}}{m^{2}-4k^{2}}c_{k}\right)&\text{if
}m\text{ is odd}\end{cases}$ $\displaystyle
b_{m}=\begin{cases}\frac{1}{2}d_{m/2}&\text{if }m\text{ is even}\\\
\delta_{m}+\frac{4}{\pi}\sum_{k=1}^{T}\frac{k(-1)^{k}\sin(\pi
m/2)}{m^{2}-4k^{2}}d_{k}&\text{if }m\text{ is odd}\end{cases}$ Minimize:
$\displaystyle\Omega$ Subject to: $\displaystyle 0\leq
w_{j},v_{j}\leq\Omega\leq 1;\quad 1\leq j\leq N,$ (5.1) $\displaystyle
L\sum_{j=1}^{N}$ $\displaystyle(w_{j}+v_{j})=1,$ (5.2) $\displaystyle
L^{2}\sum_{j=1}^{N}$ $\displaystyle(jw_{j}-(j-1)v_{j})\geq h_{1}$ (5.3)
$\displaystyle L^{3}\sum_{j=1}^{N}$ $\displaystyle(j-1)^{2}(w_{j}+v_{j})\leq
2/3+h_{2}^{2}/2,$ (5.4)
$\displaystyle\frac{L}{2}\sum_{j=1}^{N}\alpha_{j,m}^{-}(w_{j}+v_{j})$
$\displaystyle\leq\frac{4\sin\left(m\pi/2\right)}{m\pi}a_{m}-2(a_{m}^{2}+b_{m}^{2});\quad
1\leq m\leq 2R,$ (5.5)
$\displaystyle\frac{L}{2}\sum_{j=1}^{N}(\beta_{j,m}^{-}w_{j}-\beta_{j,m}^{+}v_{j})$
$\displaystyle\leq-\frac{8}{m\pi}\sin\left(m\pi/2\right)b_{m};\quad 1\leq
m\leq 2R,$ (5.6)
$\displaystyle\frac{L}{2}\sum_{j=1}^{N}(\beta_{j,m}^{+}w_{j}-\beta_{j,m}^{-}v_{j})$
$\displaystyle\geq-\frac{8}{m\pi}\sin\left(m\pi/2\right)b_{m};\quad 1\leq
m\leq 2R,$ (5.7) $\displaystyle|\epsilon_{2m-1}|$
$\displaystyle\leq\frac{1}{4-m^{2}/T^{2}}\cdot\frac{2m}{\pi\sqrt{6T^{3}}}\quad
1\leq m\leq R,$ (5.8) $\displaystyle|\delta_{2m-1}|$
$\displaystyle\leq\frac{1}{4-m^{2}/T^{2}}\cdot\frac{4}{\pi\sqrt{2T}}\quad
1\leq m\leq R,$ (5.9) $\displaystyle|c_{k}|,$ $\displaystyle\
|d_{k}|\leq\frac{2}{\pi}\quad 1\leq k\leq T,$ (5.10)
$\displaystyle\sum_{k=1}^{T}(c_{k}^{2}+d_{k}^{2})\leq 1/2,$ (5.11)
$\displaystyle p_{1}\leq c_{1}\leq p_{2},\quad q_{1}\leq d_{1}\leq q_{2},$
(5.12) $\displaystyle\frac{L}{2}$
$\displaystyle\sum_{j=1}^{N}\alpha_{j,2}^{+}(w_{j}+v_{j})\geq-\frac{1}{2}(p_{2}^{2}+\max\\{q_{1}^{2},q_{2}^{2}\\}).$
(5.13)

Our next proposition shows how the input and output of the convex program
relate to an $f(x),M(x)$ pair of functions.

######  Proposition 9.

Let $N,T,R$ be arbitrary positive integers, and
$h_{1},h_{2},p_{1},p_{2},q_{1},q_{2}$ be real numbers. Let $\Omega^{*}$ be the
optimum of the above program with this choice of input. Suppose that
$f(x),M(x)$ is as in (2.1) and satisfies

  1. (i)

$0\leq h_{1}\leq E(M)\leq h_{2}$,

  2. (ii)

$0\leq p_{1}\leq\int_{-1}^{1}\cos(\pi x)f(x)\ dx\leq p_{2}$,

  3. (iii)

$q_{1}\leq\int_{-1}^{1}\sin(\pi x)f(x)\ dx\leq q_{2}$.

Then $\|M\|_{\infty}\geq\Omega^{*}$.

###### Proof.

Our strategy is to show that any $f(x),M(x)$ satisfying the above hypotheses
gives a feasible assignment of variables such that $\Omega\leq\|M\|_{\infty}$.
Let $f(x),M(x)$ be as in (2.1) such that (i),(ii),(iii) above are also
satisfied. We will show that the following choice of variables is feasible.
Set the variable $\Omega=\|M\|_{\infty}$. For each $1\leq j\leq N$ set

$w_{j}=\frac{1}{L}\int_{(j-1)L}^{jL}M(x)\ dx\quad\text{and}\quad
v_{j}=\frac{1}{L}\int_{-jL}^{-(j-1)L}M(x)\ dx.$

For all $k\geq 1$ set

$c_{k}=\int_{-1}^{1}\cos(\pi kx)f(x)\ dx\quad\text{and}\quad
d_{k}=\int_{-1}^{1}\sin(\pi kx)f(x)\ dx.$ (5.14)

The variables of the program $c_{k},d_{k}$ only run from the indices $1\leq
k\leq T$, but we define $c_{k},d_{k}$ for $k\geq T+1$ to aid in our definition
of the last two types of variable. For each $1\leq m\leq R$ set

$\epsilon_{2m-1}=\frac{2m(-1)^{m+1}}{\pi}\sum_{k=T+1}^{\infty}\frac{(-1)^{k}}{(2m-1)^{2}-4k^{2}}c_{k},\quad\text{and}$
$\delta_{2m-1}=\frac{4(-1)^{m+1}}{\pi}\sum_{k=T+1}^{\infty}\frac{k(-1)^{k}}{(2m-1)^{2}-4k^{2}}d_{k}.$

We’ll now show that this assignment of variables is feasible. Constraint (5.1)
follows immediately from the definitions; the average of $M(x)$ on an interval
cannot exceed the maximum. The other constraints are satisfied for reasons
contained in the lemmas of Section 3, or hypotheses (i),(ii),(iii). The
dependency of constraints on corresponding lemma(s) is outlined in Table 1.

  * •

Constraint (5.2) follows from (3.8), i.e. because $\int_{-1}^{1}M(x)\ dx=1$.

  * •

Constraints (5.3) and (5.4) follow from Lemma 7 and hypothesis (i). The
constraints represent bounds on the mean and second moment of $M(x)$,
respectively.

  * •

By Lemma 3, the righthand side of constraint (5.5) is the $m^{th}$ cosine
Fourier coefficient of $M(x)$. By Lemma 5, the lefthand side of (5.5) is a
lower bound on this Fourier coefficient.

  * •

By Lemma 3, the righthand side of constraints (5.6) and (5.7) are the $m^{th}$
sine Fourier coefficient of $M(x)$. By Lemma 5, the righthand sides of (5.6)
and (5.7) are lower and upper bounds, respectively, on this Fourier
coefficient.

  * •

Constraints (5.8) and (5.9) follow from Lemma 4.

  * •

Constraint (5.10) follows from (5.14) since $f(x)\in[0,1]$ and $\|f\|_{1}=1$.

  * •

Constraint (5.11) follows from Parseval’s identity, in particular equation
(3.7).

  * •

The left constraint of (5.12) follows from hypothesis (ii), since the integer
in (ii) is precisely $c_{1}$. Similarly, the right constraint of (5.12)
follows from hypothesis (iii).

  * •

By Lemma 3, in particular (3.3) and (3.5), the second cosine Fourier
coefficient of $M(x)$ is

$A_{2}=\frac{1}{2}\int_{-2}^{2}\cos(\pi x)\
dx=-\frac{1}{2}(c_{1}^{2}+d_{1}^{2}).$

From constraint (5.12) we see that
$-\frac{1}{2}(p_{2}^{2}+\max\\{q_{1}^{2},q_{2}^{2}\\})$ is a lower bound on
the righthand side above. Also, from Lemma 5 we see that the lefthand side of
constraint (5.13) is an upper bound on the lefthand side above.

∎

Constraint | Follows from
---|---
(5.2) | (3.8)
(5.3), (5.4) | Lemma 7 and (i)
(5.5) | Lemma 3: (3.5) and Lemma 5
(5.6), (5.7) | Lemma 3: (3.6) and Lemma 5
(5.8), (5.9) | Lemma 4
(5.10) | (5.14)
(5.11) | (3.7)
(5.12) | (ii) and (iii)
(5.13) | Lemma 3: (3.5), Lemma 5, (ii) and (iii)
Table 1: Constraint feasibility

For the remainder of this paper, let $f^{\ast},M^{\ast}$ be an optimal pair in
the sense that $\|M^{\ast}\|_{\infty}=~{}\mu$. Also denote the first sine and
cosine Fourier coefficients of $f^{\ast}$ by $c_{1}^{\ast}$ and
$d_{1}^{\ast}$, i.e.

$c_{1}^{\ast}=\int_{-1}^{1}\cos(\pi x)f^{\ast}(x)\ dx,\quad\text{}\quad
d_{1}^{\ast}=\int_{-1}^{1}\sin(\pi x)f^{\ast}(x)\ dx.$

Note that $f^{\ast}(x)$, $f^{\ast}(-x)$, and $1-f^{\ast}(x)$ are all also
optimal. This means that without loss of generality, we can assume that
$E(M^{\ast})\geq 0$ and $c_{1}^{\ast}\geq 0$. It’s also easy to see that
$E(M^{*})\leq 2$ and $|c_{1}^{*}|,|d_{1}^{*}|\leq 1$. If we choose the inputs

$(h_{1},h_{2})=(0,2),\quad(p_{1},p_{2})=(0,1),\quad(q_{1},q_{2})=(-1,1),$
(5.15)

then the optimum of our convex program with this input gives a lower bound on
$\mu$. However, the optimum ends up close to 0.25 for any choice of $N,T,R$.
In order to use our program to give a good bound on $\mu$, we will need a
‘divide and conquer’ strategy of breaking up the valid ranges of parameters
shown in (5.15) into small chunks. The minimum of all the optimums over these
smaller intervals will be our lower bound on $\mu$.

###  5.1 Dual program output

As was the case with our simpler linear program in Section 4, it is best to
choose the parameter $N$ to be fairly large, i.e. at least 2000. This rules
out the use of exact solver algorithms, but numerical solvers are still fast
enough for this purpose. To guarantee the correctness of our output, we will
find feasible points in the interior of the dual program space, sufficiently
far from the boundary to compensate for any floating-point arithmetic errors.
The dual of a convex quadratically constrained problem is easiest to calculate
by first reformulating the primal program as a second order cone program
(SOCP). The dual of a SOCP is relatively simple to write down. We have placed
the details of these steps in two appendices. In Appendix II we explicitly
write down the dual program and discuss our post-processing verification step
to ensure that even if worst-case floating point arithmetic errors occur, the
assignments of dual variables used are definitely feasible. In Table 2 we
display the value of the objective function of the dual program for a verified
feasible point in the dual space for several choices of input. Note that we
have used the ‘divide and conquer’ strategy mentioned above to narrow down the
location of $E(M^{\ast}),c_{1}^{\ast}$ and $d_{1}^{\ast}$.

Parameter assignment $N,T,R=10000,4000,10$ | Optimum lower bound
---|---
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0.75,2),(0,1),(-1,1)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0.4,0.75),(0,1),(-1,1)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0.2,0.4),(0,1),(-1,1)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0.1,0.2),(0,1),(-1,1)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0.08,0.1),(0,1),(-1,1)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0,0.08),(0,1),(-1,-0.05)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0,0.08),(0,1),(-0.05,-0.025)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0,0.08),(0,1),(0.05,1)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0,0.08),(0,1),(0.025,0.05)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0,0.08),(0,0.25),(-0.025,0.025)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0,0.08),(0.25,0.3),(-0.025,0.025)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0,0.08),(0.3,0.33),(-0.025,0.025)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0,0.08),(0.5,1),(-0.025,0.025)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0,0.08),(0.45,0.5),(-0.025,0.025)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0.06,0.08),(0.33,0.45),(-0.025,0.025)$ | 0.38
$N,T,R=20000,5000,10$ |
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0.0,0.06),(0.33,0.45),(-0.025,-0.02)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0.0,0.06),(0.33,0.45),(0.02,0.025)$ | 0.38
$(h_{1},h_{2}),(p_{1},p_{2}),(q_{1},q_{2})=(0.0,0.06),(0.33,0.35),(-0.02,0.02)$ | 0.37925
Table 2: Dual program output I

The data of the first line of Table 2 shows that either $\mu\geq 0.38$ or
$E(M^{\ast})\leq 0.75$. Combining all data from Table 2 shows that either
$\mu\geq 0.37925$ or

$0\leq E(M^{\ast})\leq 0.06,\quad 0.35\leq c_{1}^{\ast}\leq
0.45,\quad\text{and }-0.02\leq d_{1}^{\ast}\leq 0.02.$ (5.16)

We can proceed in the same way by dividing the above intervals into small
pieces and finding feasible points for each of the corresponding inputs. The
drawback to this approach is that in order to achieve a lower bound close to
0.379, many hundreds of feasible points need to be computed and verified.
Instead, we can use the observation that the parameters
$h_{1},h_{2},p_{1},p_{2}$ are not a part of the constraints in the dual
program, i.e. they only affect the objective function. As a result, for any
choice of input $N,T,R,h_{1},h_{2},p_{1},p_{2},q_{1},q_{2}$ and a feasible
assignment of dual variables, we have a lower bound on the optimum of the dual
program for any choice of $h_{1},h_{2},p_{1},p_{2}$ by reusing the variable
assignment, and simply re-computing the objective function with the changed
values of $h_{1},h_{2},p_{1},p_{2}$. A precise statement, proof, and example
of this idea is given in Appendix II. We will apply this technique by first
calculating a feasible point in the dual with input such that $h=h_{1}=h_{2}$
and $p=p_{1}=p_{2}$. Next we determine by how much can $(h,p)$ change while
keeping the rest of the feasible point data fixed so that the objective
function is always at least 0.379005. Since the dependence of the objective
function on $h$ and $p$ is quadratic, the region for which the objective is at
least 0.379005 will be an ellipse on $(h,p)$-axes. We compute seven feasible
points such that the union of the ellipses described above covers the
remaining region described in (5.16). The input of these feasible points is
described in Table 3. The covering ellipses are shown in Figure 1.

Label/Colour in Figure 1 | Initial parameter assignment | Initial objective value
---|---|---
1/Green |  $h=0.015$, $p=0.381$ | 0.37905
2/Blue |  $h=0.015$, $p=0.385$ | 0.37905
3/Red |  $h=0.02$, $p=0.375$ | 0.37905
4/Purple |  $h=0.004$, $p=0.3875$ | 0.37905
5/Light green |  $h=0$, $p=0.4$ | 0.3791
6/Orange |  $h=0$, $p=0.381$ | 0.3791
7/Light blue |  $h=0.03$, $p=0.375$ | 0.3794
Table 3: Dual program output II
$N,T,R=25000,7000,10$, and $(q_{1},q_{2})=(-0.02,0.02)$ Figure 1: Lower bound
of 0.379005

The full variable assignments of all feasible solutions used in this section
are available upon request to the author. We conclude that the Theorem 1 bound
$\mu\geq 0.379005$ is now verified.

##  6 Concluding remarks

We expect that by computing more feasible solutions, using larger values of
$N,T,R$, and using more accurate floating point calculations, that our lower
bound of 0.379005 can be improved. Using the input $N,T,R=25000,7000,10$ and

$h_{1}=h_{2}=0.015,\quad p_{1}=p_{2}=0.381,\quad-q_{1}=q_{2}=0.02,$

we were able to find a feasible point with objective 0.37905, but not with
objective 0.3791. This seems to indicate that the limit of this method is not
much larger than 0.379. We also expect that the optimal function $f^{\ast}(x)$
is even. A proof of this would also improve the lower bound on $\mu$, since we
could always take $h_{1}=h_{2}=q_{1}=q_{2}=0$ as part of the input in our
convex program.

Acknowledgements. The author thanks József Solymosi and Josh Zahl for careful
reading of this work and providing valuable suggestions.

## References

  * [1] P. Erdős, _Some remarks on number theory_ (Hebrew, English summary), Riveon Lematematika, 9 (1955) 45–48; MR 17, 460.
  * [2] R. K. Guy, _Unsolved Problems in Number Theory_ , third ed., _Problem Books in Math_., Springer-Verlag, New York, 2004, sect. C17; MR2076335.
  * [3] J.K. Haugland, _Advances in the minimum overlap problem_ , Journal of Number Theory 58 (1996), no 1, 71–78. MR1387725
  * [4] J.K. Haugland, _The minimum overlap problem revisited_ , arXiv:1609.08000 [math.GM], (2016).
  * [5] M.S. Lobo, L. Vandenberghe, S. Boyd, H. Lebret, _Applications of second order cone programming_ , Linear Algebra Appl. 284 (1) (1998) 193–228. MR1655138
  * [6] N.J. Higham, _The accuracy of floating point summation_ , SIAM J. Sci. Comput. 14 (1993) 78–799. MR1223274
  * [7] L. Moser, _On the minimum overlap problem of Erdős_ , Acta Arith. 5 (1959), 117–119. MR0106864
  * [8] L. Moser and M. G. Murdeshwar, On the overlap of a function with the translation of its complement, Colloq. Math. 15 (1966), 93–97. MR0196023  Department of Mathematics
The University of British Columbia
Room 121, 1984 Mathematics Road
Vancouver, BC
Canada V6T 1Z2
<EMAIL_ADDRESS>

##  7 Appendix I: Primal program as a SOCP

In order to construct the dual program of the convex program in Section 5 we
first reformulate this primal program as a second order cone program (SOCP).
In Appendix II, we reuse the data involved in the primal program to construct
the dual SOCP. The input of both the primal and the dual is the same as the
input of the convex program in Section 5. The constraints in the primal SOCP
are the exact same as the constraints in Section 5. The only difference is
notation of variables and that the quadratic constraints must be rearranged to
become second order cone constraints. Throughout, it will be convenient to use
square brackets to describe individual elements of vectors and arrays. For
example $A[i,j]=A_{ij}$ denotes the $i,j^{th}$ entry.

Input:  $N,L=2/N,T,R,h_{1},h_{2},p_{1},p_{2},q_{1},q_{2}$

Variables:  A $(2N+2T+2R+1)\times 1$ vector variable $X$. The entries of $X$
correspond to the variables in the original convex program. This
correspondence is described in the following table of variable expressions.
The entry $X_{0}$ corresponds to variable $\Omega$ in the original program.

Variable expressions and data:  Variable expressions and data in the primal
and dual (in Appendix II) will be arranged in arrays and vectors. See Table 4
for the expressions and Table 5 for the data. In the “Description” column we
will indicate how the array or vector is indexed. We use the notation $[a,b]$
to indicate the set of integers between $a$ and $b$ inclusively, and
$[1,a]=[a]$. For example, an $[a]\times[2,b]$ array $A$ will have entries
$A[i,j]$ for $1\leq i\leq a$ and $2\leq j\leq b$.

Objective: minimize $\Phi^{T}X=X_{0}$

Constraints:

$\displaystyle\big{\|}\text{A\textsubscript{coscone}}[m]X+\text{b\textsubscript{coscone}}[m]\big{\|}_{2}$
$\displaystyle\leq\text{c${}^{T}$\textsubscript{coscone}}[m]X+\text{d\textsubscript{coscone}}[m],\text{
for all }1\leq m\leq 2R$
$\displaystyle\big{\|}\text{A\textsubscript{par}}X\big{\|}_{2}$
$\displaystyle\leq\text{d\textsubscript{par}},$
$\displaystyle\text{c${}^{T}$\textsubscript{obnd}}X+\text{d\textsubscript{obnd}}$
$\displaystyle\geq 0,$
$\displaystyle\text{c${}^{T}$\textsubscript{wbnd}}[i,j]X$ $\displaystyle\geq
0,\text{ for all }1\leq i\leq 2,\ 1\leq j\leq N,$
$\displaystyle\text{c${}^{T}$\textsubscript{vbnd}}[i,j]X$ $\displaystyle\geq
0,\text{ for all }1\leq i\leq 2,\ 1\leq j\leq N,$
$\displaystyle\text{c${}^{T}$\textsubscript{sum}}[i]X+\text{d\textsubscript{sum}}[i]$
$\displaystyle\geq 0,\text{ for all }1\leq i\leq 2,$
$\displaystyle\text{c${}^{T}$\textsubscript{mean}}X+\text{d\textsubscript{mean}}$
$\displaystyle\geq 0,$
$\displaystyle\text{c${}^{T}$\textsubscript{mome}}X+\text{d\textsubscript{mome}}$
$\displaystyle\geq 0,$ $\displaystyle\text{c${}^{T}$\textsubscript{sin-
lower}}[m]X$ $\displaystyle\geq 0,\text{ for all }1\leq m\leq 2R$
$\displaystyle\text{c${}^{T}$\textsubscript{sin-upper}}[m]X$
$\displaystyle\geq 0,\text{ for all }1\leq m\leq 2R$
$\displaystyle\text{c${}^{T}$\textsubscript{ckbnd}}[i,k]X+\text{d\textsubscript{ckbnd}}[i,k]$
$\displaystyle\geq 0,\text{ for all }1\leq i\leq 2,\ 1\leq k\leq T,$
$\displaystyle\text{c${}^{T}$\textsubscript{dkbnd}}[i,k]X+\text{d\textsubscript{dkbnd}}[i,k]$
$\displaystyle\geq 0,\text{ for all }1\leq i\leq 2,\ 1\leq k\leq T,$
$\displaystyle\text{c${}^{T}$\textsubscript{c1bnd}}[i]X+\text{d\textsubscript{c1bnd}}[i]$
$\displaystyle\geq 0,\text{ for all }1\leq i\leq 2,$
$\displaystyle\text{c${}^{T}$\textsubscript{d1bnd}}[i]X+\text{d\textsubscript{d1bnd}}[i]$
$\displaystyle\geq 0,\text{ for all }1\leq i\leq 2,$
$\displaystyle\text{c${}^{T}$\textsubscript{ep}}[i,m]X+\text{d\textsubscript{ep}}[i,m]$
$\displaystyle\geq 0,\text{ for all }1\leq i\leq 2,\ 1\leq m\leq R,$
$\displaystyle\text{c${}^{T}$\textsubscript{del}}[i,m]X+\text{d\textsubscript{del}}[i,m]$
$\displaystyle\geq 0,\text{ for all }1\leq i\leq 2,\ 1\leq m\leq R,$
$\displaystyle\text{c${}^{T}$\textsubscript{cosup}}X+\text{d\textsubscript{cosup}}$
$\displaystyle\geq 0.$

The set of constraints above is precisely the same as our program in Section
5. For example, if both sides of the first constraint above are squared and
simplified, we will obtain the constraint from the original convex program
(5.5).

Name(s) | Description | Defining property
---|---|---
$w,v$ |  $[N]$-expression vector |  $w_{j}=X_{j}$, $v_{j}=X_{N+j}$ for $1\leq j\leq N$
$c,d$ |  $[T]$-expression vector |  $c_{k}=X_{2N+k}$, $d_{k}=X_{2N+T+k}$ for $1\leq k\leq T$
$\epsilon,\delta$ |  $[R]$-expression vector |  $\epsilon_{m}=X_{2N+2T+m}$, $\delta_{m}=X_{2N+2T+R+m}$ for $1\leq m\leq R$
$a_{m}^{*}$ |  $[2R]$-expression vector | $a_{m}^{*}=\begin{cases}\frac{1}{2}c_{m/2}&\text{if }m\text{ is even}\\\ \epsilon_{m}+\frac{2m\sin(\pi m/2)}{\pi}\sum_{k=1}^{T}\frac{(-1)^{k}}{m^{2}-4k^{2}}c_{k}&\text{if }m\text{ is odd}\end{cases}$
$b_{m}$ |  $[2R]$-expression vector | $b_{m}=\begin{cases}\frac{1}{2}d_{m/2}&\text{if }m\text{ is even}\\\ \delta_{m}+\frac{4}{\pi}\sum_{k=1}^{T}\frac{k(-1)^{k}\sin(\pi m/2)}{m^{2}-4k^{2}}d_{k}&\text{if }m\text{ is odd}\end{cases}$
FcosLB |  $[2R]$-expression vector | FcosLB$[m]=\frac{L}{2}\sum_{j=1}^{N}\alpha_{j,m}^{-}(w_{j}+v_{j})$
FcosUB |  $[2R]$-expression vector | FcosUB$[m]=\frac{L}{2}\sum_{j=1}^{N}\alpha_{j,m}^{+}(w_{j}+v_{j})$
FsinLB |  $[2R]$-expression vector | FsinUB$[m]=\frac{L}{2}\sum_{j=1}^{N}(\beta_{j,m}^{-}w_{j}-\beta_{j,m}^{+}v_{j})$
FsinUB |  $[2R]$-expression vector | FsinUB$[m]=\frac{L}{2}\sum_{j=1}^{N}(\beta_{j,m}^{+}w_{j}-\beta_{j,m}^{-}v_{j})$
Table 4: Variable expressions for SOCP

Remark: we will continue to use the values assigned to $\alpha_{j,m}$,
$\beta_{j,m}$ in Section 5.

Name | Description | Defining property
---|---|---
$E$ | Integer | $E=2N+2T+2R$
$\Phi$ |  $[0,E]$-vector |  $\Phi_{0}=1$, $\Phi_{j}=0$ if $1\leq j\leq E$
Acoscone |  $[2R]\times[3]\times[0,E]$ array |  Acoscone$[m,1]X=\frac{\sin(m\pi/2)a^{*}_{m}}{m\pi}-$FcosLB$[m]/2$ Acoscone$[m,2]X=a^{*}_{m}$ Acoscone$[m,3]X=b_{m}$
bcoscone |  $[2R]\times[3]$ array |  bcoscone$[m,1]=-1/2+2\sin^{2}(\pi m/2)/(m\pi)^{2}$ bcoscone $[m,2]=\sin(\pi m/2)/(m\pi)$ bcoscone $[m,3]=0$
ccoscone |  $[2R]\times[0,E]$ array |  cTcoscone$[m]X=\frac{\sin(m\pi/2)a^{*}_{m}}{m\pi}-$FcosLB$[m]/2$
dcoscone |  $[2R]$-vector |  dcoscone $[m]=1/2+2\sin^{2}(\pi m/2)/(m\pi)^{2}$
Apar |  $[2T]\times[0,E]$ array |  Apar$[k]X=c_{k}$, and Apar$[T+k]X=d_{k}$ for all $1\leq k\leq T$
dpar | Real |  dpar $=1/\sqrt{2}$
cobnd |  $[0,E]$-vector |  cTobnd$X=-\Omega$
dobnd | Real |  dobnd$=1$
cwbnd |  $[2]\times[N]\times[0,E]$ array |  cTwbnd$[1,j]X=\Omega-w_{j}$, for all $1\leq j\leq N$, and cwbnd$[2,j]X=w_{j}$
cvbnd |  $[2]\times[N]\times[0,E]$ array |  cTvbnd$[1,j]X=\Omega-v_{j}$, for all $1\leq j\leq N$, and cvbnd$[2,j]X=v_{j}$
csum |  $[2]\times[0,E]$ array |  cTsum$[i]X=(-1)^{i+1}\sum_{j=1}^{N}(X_{j}+X_{N+j})$, for $i=1,2$
dsum | [2]-vector |  dsum$[i]=(-1)^{i}N/2$, for $i=1,2$
cmean |  $[0,E]$-vector |  cTmean$X=L\sum_{j=1}^{N}(jX_{j}-(j-1)X_{j-1})$
dmean | Real | $-h_{1}N/2$
cmome |  $[0,E]$-vector |  cTmome$X=-L^{2}\sum_{j=1}^{N}(j-1)^{2}(X_{j}+X_{N+j})$
dmome | Real | $(2/3+h_{2}^{2}/2)N/2$
csin-lower |  $[2R]\times[0,E]$ array |  cTsin-lower$X=-\frac{8}{m\pi}\sin\left(m\pi/2\right)b_{m}-$FsinLB$[m]$
csin-upper |  $[2R]\times[0,E]$ array |  cTsin-upper$X=\frac{8}{m\pi}\sin\left(m\pi/2\right)b_{m}+$FsinLB$[m]$
cckbnd |  $[2]\times[T]\times[0,E]$ array |  cTckbnd$[i,k]X=(-1)^{i+1}c_{k}$ for $i=1,2$ and $1\leq k\leq T$
dckbnd |  $[2]\times[T]$ array |  dckbnd$[i,k]=2/\pi$ for $i=1,2$ and $1\leq k\leq T$
cdkbnd |  $[2]\times[T]\times[0,E]$ array |  cTdkbnd$[i,k]X=(-1)^{i+1}d_{k}$ for $i=1,2$ and $1\leq k\leq T$
ddkbnd |  $[2]\times[T]$ array |  ddkbnd$[i,k]=2/\pi$ for $i=1,2$ and $1\leq k\leq T$
cc1bnd |  $[2]\times[0,E]$ array |  cTc1bnd$[i]X=(-1)^{i+1}c_{1}$ for $i=1,2$
dc1bnd | [2]-vector |  dckbnd$=[-p_{1},p_{2}]$
cd1bnd |  $[2]\times[0,E]$ array |  cTd1bnd$[i]X=(-1)^{i+1}d_{1}$ for $i=1,2$
dd1bnd | [2]-vector |  ddkbnd$=[-q_{1},q_{2}]$
cep |  $[2]\times[R]\times[0,E]$ array |  cTep$[i,m]X=(-1)^{i+1}\epsilon_{m}$ for $i=1,2$ and $1\leq m\leq R$
dep |  $[2]\times[R]$ array |  dckbnd$[i,m]=\frac{1}{4-m^{2}/T^{2}}\cdot\frac{2m}{\pi\sqrt{6T^{3}}}$ for $i=1,2$ and $1\leq m\leq R$
cdel |  $[2]\times[R]\times[0,E]$ array |  cTdel$[i,m]X=(-1)^{i+1}\delta_{m}$ for $i=1,2$ and $1\leq m\leq R$
ddel |  $[2]\times[R]$ array |  ddkbnd$[i,m]=\frac{1}{4-m^{2}/T^{2}}\cdot\frac{4}{\pi\sqrt{2T}}$ for $i=1,2$ and $1\leq m\leq R$
ccosup |  $[0,E]$-vector |  cTcosup$X=$FcosUB$[2]$
dcosup | Real |  dcosup$=\frac{N}{2}(p_{2}^{2}+\max\\{q_{1}^{2},q_{2}^{2}\\})$.
Table 5: Data for SOCP

##  8 Appendix II: Dual SOCP

The dual of a SOCP can be concisely stated using the data from the primal, see
Section 4.1 of [5] for details on dual SOCPs. The standard formulation of a
dual SOCP involves equality constraints. We will eliminate some variables of
the dual SOCP so that no equality constraints are used. This will allow us to
check a particular variable assignment is far enough inside the interior of
the dual space, thereby guaranteeing that assignment is feasible in spite of
worst-case floating point arithmetic errors. We begin by reviewing the
formulation of a SOCP and its dual. The standard formulation of a SOCP takes
the form

minimize: $\displaystyle\Phi^{T}x$ subject to:
$\displaystyle\|A_{i}x+b_{i}\|\leq c_{i}^{T}x+d_{i},\quad 1\leq i\leq N,$
(8.1)

where $x$ is a $n$-vector variable, $\Phi\in\mathbb{R}^{n}$, $A_{i}$ is an
$n_{i}\times n$ matrix, $b_{i}\in\mathbb{R}^{n_{i}}$,
$c_{i}\in\mathbb{R}^{n}$, and $d_{i}\in\mathbb{R}$. We have formulated our
Appendix I primal SOCP in this way. The dual to (8) is

maximize: $\displaystyle-\sum_{i=1}^{N}(b_{i}^{T}z_{i}+d_{i}y_{i})$ subject
to: $\displaystyle\sum_{i=1}^{N}(A_{i}^{T}z+c_{i}y_{i})=\Phi$
$\displaystyle\|z_{i}\|\leq y_{i},\quad 1\leq i\leq N,$ (8.2)

where $z_{i}$ is a $n_{i}$-vector of variables, and $y_{i}$ is a nonnegative
variable. There are $n$ linear equations forming the equality constraints of
(8). For our SOCP dual, we need to eliminate the equality constraints. Suppose
that for some row $1\leq j\leq n$ of the system of equality constraints in (8)
there is an index $1\leq k\leq N$ such that vector $c_{k}$ is all zero except
for a nonzero entry at row $j$, then we can solve for the variable $y_{k}$ in
terms of the other variables:

$y_{k}=\frac{1}{c_{k}[j]}\big{(}\Phi_{j}-\sum_{\begin{subarray}{c}1\leq i\leq
N\\\ i\neq k\end{subarray}}(A^{T}_{i}z+c_{i}y_{i})[j]\big{)}\geq 0.$ (8.3)

After adding the inequality on the righthand side of (8.3) to the constraints
of program (8), we can eliminate variable $y_{k}$ and the row $j$ equality
constraint from program (8). Our primal in Appendix I has $E+1=2N+2T+2R+1$
variables, and so the corresponding dual has $E+1$ equality constraints,
corresponding to the entries of vector $\Phi$. For each $0\leq j\leq E$, there
is a ‘c’ vector with a unique nonzero entry in the $j^{th}$ row. This
collection of ‘c’ vectors allows us to eliminate all equality constraints. The
‘c’ vectors we use to eliminate the equality constraints are described in
Table 6.

###  8.1 The SOCP dual

Variables:  See Table 7.

Variable expressions:  See Table 8.

Objective: maximize obj (defined in Table 8).

Constraints:

yeobnd $\displaystyle\geq 0$
$\displaystyle\text{ye\textsubscript{wbnd\\_2}}[j]$ $\displaystyle\geq 0\text{
for all }1\leq j\leq N$ $\displaystyle\text{ye\textsubscript{vbnd\\_2}}[j]$
$\displaystyle\geq 0\text{ for all }1\leq j\leq N$
$\displaystyle\text{ye\textsubscript{ckbnd\\_2}}[k]$ $\displaystyle\geq
0\text{ for all }1\leq k\leq T$
$\displaystyle\text{ye\textsubscript{dkbnd\\_2}}[k]$ $\displaystyle\geq
0\text{ for all }1\leq k\leq T$
$\displaystyle\text{ye\textsubscript{ep\\_2}}[m]$ $\displaystyle\geq 0\text{
for all }1\leq m\leq R$ $\displaystyle\text{ye\textsubscript{del\\_2}}[m]$
$\displaystyle\geq 0\text{ for all }1\leq m\leq R$
$\displaystyle(\text{y\textsubscript{coscone}}[m])^{2}$
$\displaystyle\geq\sum_{i=1}^{3}(\text{z\textsubscript{coscone}}[m,i])^{2}\text{
for all }1\leq m\leq 2R$ $\displaystyle(\text{y\textsubscript{par}})^{2}$
$\displaystyle\geq\sum_{k=1}^{2T}(\text{z\textsubscript{par}}[k])^{2}.$

Name | Index of nonzero row
---|---
cobnd | 0
cwbnd$[2,j]$ |  $j$ for $1\leq j\leq N$
cvbnd$[2,j]$ |  $N+j$ for $1\leq j\leq N$
cckbnd$[2,j]$ |  $2N+j$ for $1\leq j\leq T$
cdkbnd$[2,j]$ |  $2N+T+j$ for $1\leq j\leq T$
cep$[2,j]$ |  $2N+2T+j$ for $1\leq j\leq R$
cdel$[2,j]$ |  $2N+2T+R+j$ for $1\leq j\leq R$
Table 6: c-vectors with one nonzero entry Name | Description
---|---
zcoscone |  $[2R]\times[3]$ variable array
ycoscone |  $[2R]$-vector of nonnegative variables
zpar |  $[2T]$-vector of variables
ypar | nonnegative variable
ywbnd_1 |  $[N]$-vector of nonnegative variables
yvbnd_1 |  $[N]$-vector of nonnegative variables
ysum |  $[2]$-vector of nonnegative variables
ymean | nonnegative variable
ymome | nonnegative variable
ysin-lower |  $[2R]$-vector of nonnegative variables
ysin-upper |  $[2R]$-vector of nonnegative variables
yckbnd_1 |  $[T]$-vector of nonnegative variables
ydkbnd_1 |  $[T]$-vector of nonnegative variables
yc1bnd |  $[2]$-vector of nonnegative variables
yd1bnd |  $[2]$-vector of nonnegative variables
yep_1 |  $[R]$-vector of nonnegative variables
ydel_1 |  $[R]$-vector of nonnegative variables
ycosup | nonnegative variable
Table 7: Variables for dual SOCP Name | Description | Definition
---|---|---
ATzcoscone |  $[0,E]$-expression vector |  ATzcoscone$[j]=\sum_{m=1}^{2R}\sum_{i=1}^{3}$Acoscone$[m,i,j]$zcoscone$[m,i]$
cycoscone |  $[0,E]$-expression vector |  cycoscone$[j]=\sum_{m=1}^{2R}$ccoscone$[m,j]$ycoscone$[m]$
ATzpar |  $[0,E]$-expression vector |  ATzpar $[j]=\sum_{k=1}^{2T}$Apar$[k,j]$zpar$[k]$
cywbnd_1 |  $[0,E]$-expression vector |  cywbnd_1 $[j]=\sum_{i=1}^{N}$cwbnd$[1,i,j]$ywbnd_1$[i]$
cyvbnd_1 |  $[0,E]$-expression vector |  cywbnd_1 $[j]=\sum_{i=1}^{N}$cvbnd$[1,i,j]$yvbnd_1$[i]$
cysum |  $[0,E]$-expression vector |  $\sum_{i=1}^{2}$cysum $[i,j]=$csum$[i,j]$ysum$[i]$
cymean |  $[0,E]$-expression vector |  cymean $[j]=$cmean$[j]$ymean
cymome |  $[0,E]$-expression vector |  cymome $[j]=$cmome$[j]$ymome
cysine |  $[0,E]$-expression vector |  cysine$[j]=\sum_{m=1}^{2R}$csin-lower$[m,j]$ysin-lower$[m]$ $+\sum_{m=1}^{2R}$csin-upper$[m,j]$ysin-upper$[m]$
cycd |  $[0,E]$-expression vector |  cycd$[j]=\sum_{m=1}^{T}$cckbnd$[1,k,j]$yckbnd_1$[k]$ $+\sum_{k=1}^{T}$cdkbnd$[1,k,j]$yckbnd_1$[k]$ $+\sum_{i=1}^{2}($cc1bnd$[i,j]$yc1bnd$[i]+$cd1bnd$[i,j]$yd1bnd$[i])$
cyepdel |  $[0,E]$-expression vector |  cyepdel$[j]=\sum_{m=1}^{R}$cep$[1,m,j]$yep_1$[m]$ $+\sum_{m=1}^{R}$cdel$[1,m,j]$ydel_1$[m]$
cycosup |  $[0,E]$-expression vector |  cycosup $[j]=$ccosup$[j]$ycosup
subtotal |  $[0,E]$-expression vector |  subtotal is the sum of all previous $[0,E]$-expression vectors in this table
yeobnd | expression |  $1-$subtotal$[0]$
yewbnd_2 |  $[N]$-expression vector |  yewbnd_2$[j]=-$ subtotal$[j]$ for $1\leq j\leq N$
yevbnd_2 |  $[N]$-expression vector |  yevbnd_2$[j]=-$ subtotal$[N+j]$ for $1\leq j\leq N$
yeckbnd_2 |  $[T]$-expression vector |  yeckbnd_2$[j]=-$ subtotal$[2N+j]$ for $1\leq j\leq T$
yedkbnd_2 |  $[T]$-expression vector |  yedkbnd_2$[j]=-$ subtotal$[2N+T+j]$ for $1\leq j\leq T$
yeep_2 |  $[R]$-expression vector |  yeep_2$[j]=-$ subtotal$[2N+2T+j]$ for $1\leq j\leq R$
yedel_2 |  $[R]$-expression vector |  yedel_2$[j]=-$ subtotal$[2N+2T+R+j]$ for $1\leq j\leq R$
bTzcoscone | expression |  bTzcoscone$=\sum_{m=1}^{2R}\sum_{i=1}^{3}$bcoscone$[m,i]$zcoscone$[m,i]$
dycoscone | expression |  dycoscone$=\sum_{k=1}^{2R}$dcoscone$[k]$ycoscone$[k]$
dypar | expression |  dypar$=$dparypar
dyobnd | expression |  dyobnd$=$dobndyeobnd
dysum | expression |  dysum$=\sum_{i=1}^{2}$dsum$[i]$ysum$[i]$
dymean | expression |  dymean$=$dmeanymean
dymome | expression |  dymome$=$dmomeymome
dycd | expression |  dycd$=\sum_{i=1}^{2}($dc1bnd$[i]$yc1bnd$[i]+$dd1bnd$[i]$yd1bnd$[i]$) $+\sum_{k=1}^{T}\big{(}$dckbnd$[1,k]$yckbnd_1$[k]+$ddkbnd$[1,k]$ydkbnd_1$[k]$ $+$dckbnd$[2,k]$yeckbnd_2$[k]+$ddkbnd$[2,k]$yedkbnd_2$[k]$)
dyepdel | expression |  dyepdel$=\sum_{m=1}^{R}($dep$[1,m]$yep_1$[m]+$ddel$[1,m]$ydel_1$[m]$) $+\sum_{m=1}^{R}($dep$[2,m]$yeep_2$[m]+$ddel$[2,m]$yedel_2$[m]$)
dycosup | expression |  dycosup$=$dcosupycosup
obj | expression |  $-1$ times the sum of the previous 10 expressions
Table 8: Variable expressions for dual SOCP

###  8.2 Feasibility verification

We will use a numerical solver to find feasible points in the dual SOCP,
thereby giving lower bounds to the primal optimum. Given an assignment of
values to the variables of the dual, we need to verify that in spite of any
floating point arithmetic errors, the constraints are satisfied. We use IBM’s
CPLEX optimization software, which employs a barrier algorithm to solve SOCP.
CPLEX uses double-precision (64-bit) arithmetic in its computations with a
rounding error unit of $u=2^{-53}$. For any $x\in\mathbb{R}$, let
$\text{fl}(x)$ be its stored double-precision value. If no overflow or
underflow occurs, we have the following bounds.

  * •

Let $x,y\in\mathbb{R}$ and $\star\in\\{+,-,\times,\div\\}$ be an operation
where $y=0$ and $\star=\div$ do not both hold, then for sum $|\delta|\leq u$:

$\text{fl}(x\star y)=(x\star y)(1+\delta).$

  * •

Let $n\in\mathbb{N}$. If $x_{1},\ldots,x_{n}\in\mathbb{R}$, and
$S_{n}=\sum_{k=1}^{n}x_{k}$, then

$\big{|}S_{n}-\text{fl}(S_{n})\big{|}\leq\frac{(n-1)u}{1-(n-1)u}\sum_{k=1}^{n}|x_{k}|.$

Details of these estimates, and improvements on them can be found in [6]. Let
$n\in\mathbb{N}$, and $x_{k},y_{k}\in\mathbb{R}$ for $k=1,\ldots,n$. The
arithmetic expressions involved in the constraints of our dual SOCP take the
form

$S=\sum_{k=1}^{n}x_{k}y_{k}.$

By the earlier two floating point estimates we have:

$\big{|}S-\text{fl}(S)\big{|}\leq\frac{(n-1)u}{1-(n-1)u}\sum_{k=1}^{n}|\text{fl}(x_{i}y_{i})|\leq\frac{(n-1)u(1+u)}{1-(n-1)u}\sum_{k=1}^{n}|x_{i}y_{i}|.$
(8.4)

After receiving a proposed assignment of dual variable values from CPLEX, we
verify that every constraint inequality is strictly satisfied by a margin of
at least the above error bound. The error bound on the righthand side of (8.4)
needs to be computed. We did this by roughly estimating the individual terms.
For example, consider the final constraint in our dual SOCP:

$(\text{y\textsubscript{par}})^{2}-\sum_{k=1}^{2T}(\text{z\textsubscript{par}}[k])^{2}\geq
0.$ (8.5)

For all feasible solutions to the dual SOCP we use in this paper, the maximum
absolute value of $\\{\text{z\textsubscript{par}}[k]\\}_{k=1}^{2T}$ is less
than 0.0005. Therefore, the error bound for (8.5) is less that $10^{-13}$. On
the other hand, the minimum value of the lefthand side of (8.5) for all
feasible solutions we use exceeds $10^{-11}$.

###  8.3 Reusing a feasible solution

By inspecting Table 5 we see that the parameters $h_{1},h_{2},p_{1},p_{2}$ are
only used in the ‘d’ type data (never in A, b, or c). From (8) and (8) we see
this means that $h_{1},h_{2},p_{1},p_{2}$ will only affect the objective
function of the dual, but not the constraints. Hence any single feasible
solution to the dual, will give a lower bound on the optimum for any choice of
$h_{1},h_{2},p_{1},p_{2}$. We make this precise below.

######  Lemma 10.

Fix a choice of input $N,T,R,h_{1},h_{2},p_{1},p_{2},q_{1},q_{2}$ for the dual
program. Suppose there exists a feasible solution for this input and let
$\overline{\emph{y}}$mean,$\overline{\emph{y}}$mome,$\overline{\emph{y}}$c1bnd,
and $\overline{\emph{y}}$cosup be the values of the dual variables
ymean,ymome,yc1bnd, and ycosup for this solution. Let
$h_{1}^{\prime},h_{2}^{\prime},p_{1}^{\prime},p_{2}^{\prime}\in\mathbb{R}$ and
$\emph{obj}(h_{1}^{\prime},h_{2}^{\prime},p_{1}^{\prime},p_{2}^{\prime})$ be
the value of the objective function for this solution and input choice
$N,T,R,h_{1}^{\prime},h_{2}^{\prime},p_{1}^{\prime},p_{2}^{\prime},q_{1},q_{2}$.
If $\emph{opt}(h_{1}^{\prime},h_{2}^{\prime},p_{1}^{\prime},p_{2}^{\prime})$
is the optimum of the dual program with input
$N,T,R,h_{1}^{\prime},h_{2}^{\prime},p_{1}^{\prime},p_{2}^{\prime},q_{1},q_{2}$
then

$\displaystyle\emph{opt}(h_{1}^{\prime},h_{2}^{\prime},p_{1}^{\prime},p_{2}^{\prime})$
$\displaystyle\geq\emph{obj}(h_{1},h_{2},p_{1},p_{2})$
$\displaystyle+\frac{N}{4}\left(2(h_{1}^{\prime}-h_{1})\overline{\emph{y}}\textsubscript{mean}+(h_{2}^{2}-(h_{2}^{\prime})^{2})\overline{\emph{y}}\textsubscript{mome}+2(p_{2}^{2}-(p_{2}^{\prime})^{2}\overline{\emph{y}}\textsubscript{cosup}\right)$
$\displaystyle\quad+(p_{1}^{\prime}-p_{1})\overline{\emph{y}}\textsubscript{c1bnd}[1]+(p_{2}-p_{2}^{\prime})\overline{\emph{y}}\textsubscript{c1bnd}[2].$
(8.6)

###### Proof.

From the definitions of Table 5 and Table 8 the value of
obj$(h_{1}^{\prime},h_{2}^{\prime},p_{1}^{\prime},p_{2}^{\prime})-\text{obj}(h_{1},h_{2},p_{1},p_{2})$
is precisely the quantity on the second two lines of (8.6). Since
opt$(h_{1}^{\prime},h_{2}^{\prime},p_{1}^{\prime},p_{2}^{\prime})\geq$
obj$(h_{1}^{\prime},h_{2}^{\prime},p_{1}^{\prime},p_{2}^{\prime})$ we have the
claimed result.

∎

We now discuss how Lemma 10 is applied. We can find a feasible point for our
dual SOCP with input $N=25000,T=7000,R=10$ and

$h_{1}=h_{2}=0.015,\quad p_{1}=p_{2}=0.385,\quad-
q_{1}=q_{2}=0.02,\quad\text{obj}=0.37905.$

This feasible point makes the following variable assignments:

ymean $\displaystyle=0.0000014902$ ymome $\displaystyle=0.00010235$ ycosup
$\displaystyle=0.000038011$ yc1bnd $\displaystyle=(0.35962,0).$

Let opt$(h_{1}^{\prime},h_{2}^{\prime},p_{1}^{\prime},p_{2}^{\prime})$ be as
defined Lemma 10. We can use this feasible point to determine a set of
$h,p\in\mathbb{R}$ such that $h,p\in\mathbb{R}$ has opt$(h,h,p,p)\geq
0.379005$. By Lemma 10, if $h,p\in\mathbb{R}$ is such that

$\displaystyle\frac{25000}{4}\big{(}2(h-0.015)$ $\displaystyle\cdot
0.0000014902+(0.015^{2}-h^{2})\cdot 0.00010235+2(0.385^{2}-p^{2})\cdot
0.000038011\big{)}$ $\displaystyle+(0.385-p)\cdot 0.35962\geq
0.379005-0.37905,$ (8.7)

then we can conclude opt$(h,h,p,p)\geq 0.379005$. The set of $(h,p)$ that
satisfy the above inequality lie inside an ellipse, shown in Figure 2.

Figure 2: A subset of the region in $(h,p)$ space where opt$(h,h,p,p)\geq
0.379005$.

This gives a consequence on the original $f,M$ functions of (2.1) by
Proposition 9. For any $f,M$ as in (2.1), put

$h=E(M),\quad p=\int_{-1}^{1}\cos(\pi x)f(x)dx,\quad\text{and}\quad
q=\int_{-1}^{1}\sin(\pi x)f(x)dx.$

If $-0.02\leq q\leq 0.02$ and $(h,p)$ defined above satisfy (8.7), then
$\|M\|_{\infty}\geq 0.379005$.