# Optical transmitter for time-bin encoding Quantum Key Distribution

Julián Morales  1,2,* M. Guadalupe Aparicio  2 Carlos F. Longo  4 Cristian L.
Arrieta  4 and Miguel A. Larotonda1,2,3  1UNIDEF, Ministerio de Defensa-
CONICET, J.B. de Lasalle 4397, 1603 Villa Martelli, Buenos Aires, Argentina
2Departamento de Física, Facultad de Ciencias Exactas y Naturales, Universidad
de Buenos Aires. Ciudad Universitaria Pabellón I, 1428 Buenos Aires, Argentina
3Departamento de Investigaciones en Láseres y Aplicaciones, CITEDEF,
Ministerio de Defensa, J.B. de Lasalle 4397, 1603 Villa Martelli, Buenos
Aires, Argentina
4Departamento de Electrónica Aplicada, CITEDEF, Ministerio de Defensa, J.B. de
Lasalle 4397, 1603 Villa Martelli, Buenos Aires, Argentina
<EMAIL_ADDRESS>
###### Abstract

We introduce an electro-optical arrangement that is able to produce time-bin
encoded symbols with the decoy state method over a standard optical fiber in
the C-band telecom window. The device consists of a specifically designed
pulse pattern generator for pulse production, a field-programmable gate array
that controls timing and synchronization. The electrical pulse output drive a
sequence of intensity modulators acting on a continuous laser that deliver
bursts of weak optical pulse pairs of discrete intensity values. Such
transmitter allows for the generation of all the quantum states needed to
implement a discrete variable Quantum Key Distribution protocol over a single-
mode fiber channel. Symbols are structured in bursts; the minimum relative
delay between pulses is 1.25 ns, and the maximum symbol rate within a burst is
200 MHz. We test the transmitter on simulated optical channels of 7 dB and 14
dB loss, obtaining maximum extractable secure key rates of 3.0 kb/s and 0.57
kb/s respectively. Time bin state parameters such as symbol rate, pulse
separation and intensity ratio between signal and decoy states can be easily
accessed and changed, allowing the transmitter to adapt to different
experimental conditions and contributing to standardization of QKD
implementations.

††journal: opticajournal††articletype: Research Article

##  1 Introduction

Quantum Key Distribution (QKD) is a cryptographic task that relies on
fundamental principles of quantum mechanics that allows for two parties to
share a random secret key. The presence of an eavesdropper trying to gain
information on the key disturbs the system and introduces measurable changes
that reveals their presence [1].

The first protocol dates back to 1984, when Charles Bennett and Gilles
Brassard introduced the BB84 protocol [2] and shortly after the first
experimental realization was demonstrated [3]. Since then, many protocols,
techniques and emerging technologies have contributed to bolster this rapidly
expanding field. Preferred channels for these quantum communications protocols
are optical fibers in the near infrared spectral region [4, 5, 6, 7] and, most
recently, open space links between ground stations and low earth orbit
satellites [8, 9, 10]. Ground based QKD protocols have evolved to simpler and
more efficient schemes combined with robust security that feature symbol rates
in the order range of the GHz [11, 12, 13, 14, 15, 16], and record length
transmission links exceeding 400 km of single mode fibers [17] for prepare-
and-measure protocols, 800 km for the novel twin-field protocols [18] and 1000
km for entanglement-based protocols [19] . Meanwhile, quantum communications
and QKD have been demonstrated on satellite-to-earth open space links, using
polarization encoding [8]. Despite all these achievements and developments,
QKD is still not a mature technology: Although solutions that can perform the
tasks on both the emitter and the receiver sides in an efficient way do exist,
these building blocks for a quantum communication system are still not
standardized. Only a few companies offer commercial (yet closed) systems for
quantum secure communications. In order to obtain a fast and efficient QKD
implementation, a few key aspects have to be considered: a fast and reliable
state preparation, a simplified experimental realization with minimum
technical requirements and its security guaranteed by quantum physics,
combined with an efficient detection scheme.

For fiber based links, the preferred qubit encoding is time-bin (arrival time
of the detected photons, relative to a fixed clock reference). In general, the
most easily implementable protocols (i.e. the ones that require minimum active
parts and processes) are also the ones that achieve highest speeds.
Furthermore, they have the advantage of being less prone to side channel
attacks, since almost every imperfection of an optical component might be
exploited as a security weakness [16, 17, 20]. Modern protocols such as
Measurement-device-independent QKD [21, 22, 23] require spectral, temporal and
polarization indistinguishability of signal pulses generated by the two
independent and distant laser sources. On the other hand, twin-field QKD [24,
25, 26, 27] adds the need for link phase stabilization. The respective
increased security and distance between nodes that these protocols offer come
at the cost of an increased experimental complexity, although much effort is
being put into these technologies [28, 29]. Regarding the detection, fast and
efficient sensing requirements have lead to alternative technologies such as
superconducting nanowire single photon detectors [30, 31], or self-
differencing techniques that increase the gating frequency of traditional
avalanche photodiodes [32, 33]. Also, minimizing the temporal multiplexing of
auxiliary signals or processes such as active interferometer stabilization can
increase the maximum detection rate.

On the other side of the link, the emitter should be able to prepare all the
quantum states in a fast and unambiguous manner. This implies shaping pulses
as symbols belonging to different state bases and the ability to prepare
signal and decoy states. For practical encoding of time-bin qubits, defined by
two temporal modes with a relative delay $\Delta T$ called early ($e$) and
late ($l$), states of the $Z$ basis are approximated using weak coherent
pulses of mean photon number $\mu=\left|\alpha\right|^{2}$:

$\displaystyle\left|\psi_{0}\right\rangle$
$\displaystyle=\left|\alpha\right\rangle_{e}\left|0\right\rangle_{l}$ (1)
$\displaystyle\left|\psi_{1}\right\rangle$
$\displaystyle=\left|0\right\rangle_{e}\left|\alpha\right\rangle_{l}$

States of the $X$ basis are superpositions of $\left|\psi_{0}\right\rangle$
and $\left|\psi_{1}\right\rangle$:
$\left|\psi_{\pm}\right\rangle=1/\sqrt{2}\left(\left|\psi_{0}\right\rangle\pm\left|\psi_{1}\right\rangle\right)$,
and correspond to a superposition of two wavepackets temporally separated by
$\Delta T$. Measurements in the $X$ basis require the use of an interferometer
with an arm unbalance of $\Delta T$: states are split into the two arms and
upon recombination, phase information can be retrieved from detections of the
central temporal bin [34, 35]. Thus, in order to avoid instabilities from
large arm unbalance, and to be able to increase the symbol rate, the temporal
bins should be set as close as possible, by minimizing $\Delta T$. This
condition imposes a large RF bandwidth for the optoelectronic components to
shape the coding symbols, regardless of the specific method used to generate
the pulses.

In this work we present a transmitter for a variable rate QKD system over an
optical fiber channel; an optical source that is capable of generating quantum
signals for a discrete variable decoy state Quantum Key Distribution protocol
with time-bin encoding. Due to their flexibility, multiple task managing and
processing power, state-of-the-art designs use either high performance field
programmable gate arrays (FPGAs) and peripherals, or RF arbitrary waveform
generators to execute all the tasks required by the communication protocol
[36, 37, 38]. Following the former approach, we generate all the timing,
triggering and synchronizing signals with a development board based on the
Xilinx Zynq-7000 FPGA, while the fast pattern that is needed for optical pulse
generation is produced with an ad-hoc high speed circuit.

The following section is devoted to the description of the electronics, opto-
electronics and driving signals needed to implement a QKD protocol based on
time-bin encoding on weak coherent pulses using a decoy state method [39, 40].
We show the performance of the transmitter in section 3.

##  2 Experimental arrangement

The devised transmitter is able to produce the necessary states to implement a
three-state protocol [41, 42, 16] with the one-decoy state method, that
implies the generation of symbols with two different mean photon numbers,
$\mu_{1}$ (signal) and $\mu_{2}$ (decoy). These states, encoded in the time-
bin degree of freedom can be expressed as follows:

$\begin{matrix}\left|\psi_{0}\right\rangle_{\mu_{1}}=\left|\sqrt{\mu_{1}}\right\rangle\left|0\right\rangle;\;&\left|\psi_{0}\right\rangle_{\mu_{2}}=\left|\sqrt{\mu_{2}}\right\rangle\left|0\right\rangle\\\
\left|\psi_{1}\right\rangle_{\mu_{1}}=\left|0\right\rangle\left|\sqrt{\mu_{1}}\right\rangle;\;&\left|\psi_{0}\right\rangle_{\mu_{2}}=\left|0\right\rangle\left|\sqrt{\mu_{2}}\right\rangle\\\
\left|\psi_{+}\right\rangle_{\mu_{1}}=1/\sqrt{2}\left(\left|\sqrt{\mu_{1}}\right\rangle\left|0\right\rangle+\left|0\right\rangle\left|\sqrt{\mu_{1}}\right\rangle\right);\;&\left|\psi_{+}\right\rangle_{\mu_{2}}=1/\sqrt{2}\left(\left|\sqrt{\mu_{2}}\right\rangle\left|0\right\rangle+\left|0\right\rangle\left|\sqrt{\mu_{2}}\right\rangle\right)\\\
\end{matrix}$ (2)

States from the computational $Z$ basis, Eq. (1) are used to generate the key,
while states $\left|\psi_{+}\right\rangle$ are used to estimate the
information obtained by an eavesdropper. An additional requirement for any
implementation of QKD with weak coherent state signals is that the phase of
each symbol must be random in order to enhance the security of the protocol
[43]. This single decoy state method has been shown to outperform the 2-decoy
protocol for almost all experimental settings under the assumption of finite
key length [44].

The optical part of the transmitter consists of a 1548 nm continuous wave (CW)
distributed feedback laser (Mitsubishi FU-641SEA) with an integrated electro-
absorption modulator (EAM), and a chain of a phase modulator (Thorlabs
LN65S-FC) and two intensity modulators (Lucent 2623NA) for phase
randomization, normalization of the mean photon number of the
$\left|\psi_{+}\right\rangle$ state and selection of signal or decoy states,
respectively (Fig. 1). A Digilent Zybo Zynq-7000 FPGA generates the main
clock, the digital signals that drive the external intensity modulators and a
synchronizing signal for detection. Since the bandwidth of the desired
patterns is larger than the frequency range attainable by the FPGA digital
outputs, optical pulses are carved out from the CW laser output using the 10
GHz built-in EAM, which is driven by a Pulse Pattern Generator (PPG)
specifically designed for this task.

Figure 1: Scheme of the proposed QKD transmitter. The EAM and the intensity
modulators IM1 and IM2 that set the mean photon values for the
$\left|\psi_{+}\right\rangle$ states and the signal and decoy states
respectively are driven by Modulator Driver Amplifiers (MDAs), a phase
modulator (PM) driven by a noise generator (NG) randomizes the phase between
symbols. ISO: optical isolator; OA: optical attenuator. PPG refers to the
Pulse Pattern Generator. Detection and state identification is done by means
of a Single Photon Counting Module (SPCM) and a time-to-digital converter
(TDC).

The PPG was designed and built in-house upon a 4 layer printed circuit board.
It is based on a PLL clocking circuit and a 3.2 Gb/s data rate serializer.
This arrangement generates a selected optical pulse pattern by converting an
8-bit parallel bus into a serial stream by means of a MC10EP446 serializer
integrated circuit (Onsemi), at twice the frequency of its clock. The PPG
accepts a clock input signal between 10 and 100 MHz, which is delivered by the
FPGA board. A NBC12430 programmable phase-locked loop clock generator (Onsemi)
synthesizes a clock signal of frequency $F_{out}$ between 400 and 800 MHz from
the input frequency to clock the serializer (Fig. 2a). The generator also
includes AC coupled differential outputs for the serial pattern and for the
parallel clock. An additional input signal (_Sync_) managed by the FPGA
synchronously enables the serial output, allowing for the decoupling between
the symbol repetition rate and the pulses width and delay, and also for burst
data structuring. Single or double pulse patterns needed to form states from
$Z$ and $X$ bases are generated by serializing 8-bit parallel strings; for the
minimum pulse separation, these strings are 10000000, 00100000 and 10100000 or
any shift of these patterns. A faster digital data transfer from the FPGA to
the serializer is currently under development, that will allow to send two
symbols per serial string. Larger delays between _early_ and _late_ pulses can
be obtained by including more _off_ bits between them; larger interferometer
unbalances on the detection side can be accommodated in this way.
Additionally, two timing signals are sent to the receiver through the
classical channel to adequately count and identify states within symbols (Fig.
2b).

Figure 2: a) Pulse Pattern Generator (PPG). A PLL clocking circuit synthesizes
a tunable multiple ($F_{\text{out}}$) of the input frequency
($F_{\text{ref}}$), which serves as the serializer clock. The initial single
or double pulse patterns are selected by setting the parallel bus
($D_{0}$-$D_{7}$) with the FPGA, and an additional input signal ($Sync$)
enables the output of the PPG and allows for structuring of the data stream.
Patterns with minimum delay between pulses are produced using the 8-bit
sequences depicted on the top right; b) Timing diagram. The output is
structured in symbol bursts. Each burst is composed by a user-defined amount
of symbols, which can be produced at a maximum rate of 200 MHz. Auxiliary
timing and counting signals are generated at the FPGA on each burst and sent
to the receiver. A low jitter counting signal synchronized with each data
symbol is generated on the GPP to identify the time-bin state of each symbol;
c) GPP board showing ECL differential serial (bottom edge) and clock (right
edge) outputs.

With the chosen configuration the PPG can generate time bin symbols as short
as 1.5 clock cycles: a couple of $\delta t=625$ ps width optical pulses
delayed $\Delta T=1.25$ ns, at a maximum symbol rate of $F_{out}/8$=200 MHz.
The specific pattern that defines whether the output symbol is either
$\left|\psi_{0}\right\rangle$, $\left|\psi_{1}\right\rangle$ or
$\left|\psi_{+}\right\rangle$ is applied in the parallel bus by the FPGA at
the symbol rate. It is worth to note that the 8 bit serial pattern allows to
code two symbols per serialized word, hence duplicating the symbol rate up to
400 MHz. The output of this pattern generator is later amplified with a
MAX3941 (Maxim Integrated) MDA and transferred to the optical domain with the
EAM acting on the laser output.

Two amplitude modulators controlled by the FPGA insert a 50% loss on the
$\left|\psi_{+}\right\rangle$ states to obtain a uniform photon rate per
symbol, and set the relative intensity $\mu_{2}/\mu_{1}$ for signal and decoy
states. Finally, an additional phase modulator driven by a 50 MHz bandwidth
noise generator ensures that the phase is randomized for each symbol.

The temporal structure of the output signal is set by the FPGA acting on the
PPG via the Sync input. Symbols can be clustered in bursts of selectable
length and delay, to allow for additional time multiplexing of phase
stabilization routines on the detector side, and also to adapt the data stream
to different detector dead times. The performance of the device together with
a demonstration of quantum state transmission through a simulated optical
channel are presented in the following section.

##  3 Experimental results

Histograms of the output optical pulses generated with the transmitter set at
a serial clock frequency of 684 MHz and a symbol rate of 5 MHz within the
burst are shown in figure 3. The ratio $\mu_{2}/\mu_{1}\approx 0.4$ is close
to the optimum for almost any channel length [44]. For the detection of single
photons we used an IDQ Id201 InGaAs/InP SPCM with an efficiency of 10% and a
time-to-digital converter (Time Tagger Ultra, Swabian Instruments) with a
temporal resolution of 42 ps. The data output was structured in bursts of 20
symbols to account for the 20 $\mu$s detector dead time. A detection window of
20 ns was set on each measurement, for both the $X$ and $Z$ bases.

Figure 3: Histograms of the measured states proposed in eq.(2). Each state was
measured by looking at a fixed symbol within the repeating burst. Valid
detections were defined using 0.8 ns windows for each time-bin, shown on the
top right panel with green (_early_) and red (_late_) bars. Phantom lines on
states of the $Z$ basis show the temporal bin of complementary states.

The transmitter was put under test with two simulated channels of 7 dB and 14
dB total loss, corresponding to fiber optical link lengths of 35 km and 70 km,
respectively. For the experimental results presented here, a 300 seconds
measurement was performed for each condition, in which an average of 273
million symbols were sent. The mean photon numbers per symbol at the output of
the source are $\mu_{1}=0.50$ and $\mu_{2}=0.19$ on both cases, and the
optimized probabilities of emitting these states are $p_{\mu_{1}}=0.63$ and
$p_{\mu_{2}}=0.37$. The probability of emitting states of the $Z$ basis was
set at $p_{Z}=0.9$.

The bit error in the $Z$ basis $Q_{Z}$ is obtained in a straightforward way by
calculating the ratio between the wrong detections and the total number of
detections. The $\left|\psi_{+}\right\rangle$ state is detected and analyzed
using an actively stabilized, unbalanced Faraday-Michelson interferometer,
which gives a three-pulse output where the interference effect is present on
the central pulse. We follow the procedure described in [38] to estimate the
error rate in the $X$ basis, $Q_{X}$. An upper bound on the phase error rate
for states of the $Z$ basis $\phi_{Z}$ can be obtained using the calculations
described in [44] and the QBER estimations $Q_{Z}$ and $Q_{X}$. The
interferometer was actively stabilized using a modified gradient descent
algorithm that maximizes the count rate on the central pulse by acting on a
piezoelectric fiber stretcher. Such optimization procedure must be performed
every 100 seconds and it is temporally multiplexed between data streams. The
bit error rate $Q_{Z}$ and the phase error rate $\phi_{Z}$, together with the
estimated secret key rates obtained for the two attenuation conditions are
summarized in figure 4. The intrinsic visibility of the interferometer was
estimated in 0.98, implying that most of the error in the $X$ basis
measurements is due to the detector noise and jitter. The secure key rate can
be obtained from the repetition rate of the source and the lower bound of the
secret key length in a finite-key scenario, as described in Ref [44].

Figure 4: Bit and phase error rates obtained for two different simulated
lengths of standard single mode fiber, together with the extractable SKR.

For an attenuation equivalent to a fiber length of 35 km we obtain bit and
phase error of the order of 3% and 6% respectively, and a secure key rate of
3.0 kb per second; when the attenuation is doubled however, the detector dark
counts combined with residual imperfections of the $X$ basis detection scheme
increase the error rates leading to a reduced SKR of 570 bits per second.

##  4 Conclusion

The results presented above demonstrate the use of an electro-optical
transmitter for time-bin discrete variable QKD. The configuration can produce
the six states needed to implement a three-state protocol with the decoy state
method. Fast electrical patterns are delivered with a 8-bit serializer fed by
a PLL-synthesized clock, while the timing, gating and low bandwidth
synchronizing tasks are implemented within the FPGA board. The specific
serializer circuit that was used in this transmitter can deliver output data
rates of up to 3.2 GHz. This pattern enables the use of an interferometer with
a short delay unbalance for detection in the $X$ basis, by imposing a temporal
delay equal to the pulse separation of 625 ps. The arm unbalance can be
reduced to an optical fiber segment of only 6.25 cm provided a Michelson-
Faraday interferometer is used. The 8-bit variable rate also allows for a
flexible output that can accommodate to different technical requirements
imposed by the overall channel loss and by the speed and dead time of the
detection technology. Furthermore, the serial output can be adapted in a
straightforward way to implement high dimensional quantum communication
protocols with $d=4$ time bin _qudits_ [45, 46]. The device was tested on a
three-state decoy method quantum communication scheme over simulated channels
of 35 km and 70 km single mode fiber obtaining secure key yields of $1.1\times
10^{-5}$ and $2.1\times 10^{-6}$ bits per emitted symbol respectively. The
presented transmitter can be easily combined with a low bandwidth pulse
pattern generator or FPGA board to generate time bin quantum states at a high
rate for standardized QKD applications.

Funding Content in the funding section will be generated entirely from details
submitted to Prism.

Acknowledgments

Disclosures The authors declare no conflicts of interest.

Data availability Data underlying the results presented in this paper are not
publicly available at this time but may be obtained from the authors upon
reasonable request.

## References

  * [1] N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Reviews of modern physics 74, 145 (2002).
  * [2] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” in _Proc. of IEEE Int. Conf. on Comp. Sys. and Signal Proc., Dec. 1984,_ (1984).
  * [3] C. H. Bennett, F. Bessette, G. Brassard, L. Salvail, and J. Smolin, “Experimental quantum cryptography,” Journal of cryptology 5, 3–28 (1992).
  * [4] S. Wang, W. Chen, Z.-Q. Yin, H.-W. Li, D.-Y. He, Y.-H. Li, Z. Zhou, X.-T. Song, F.-Y. Li, D. Wang _et al._ , “Field and long-term demonstration of a wide area quantum key distribution network,” Optics express 22, 21739–21756 (2014).
  * [5] Q. Zhang, F. Xu, L. Li, N.-L. Liu, and J.-W. Pan, “Quantum information research in china,” Quantum Science and Technology 4, 040503 (2019).
  * [6] Y. Mao, B.-X. Wang, C. Zhao, G. Wang, R. Wang, H. Wang, F. Zhou, J. Nie, Q. Chen, Y. Zhao _et al._ , “Integrating quantum key distribution with classical communications in backbone fiber network,” Optics express 26, 6010–6020 (2018).
  * [7] J.-P. Chen, C. Zhang, Y. Liu, C. Jiang, W.-J. Zhang, Z.-Y. Han, S.-Z. Ma, X.-L. Hu, Y.-H. Li, H. Liu _et al._ , “Twin-field quantum key distribution over a 511 km optical fibre linking two distant metropolitan areas,” Nature Photonics 15, 570–575 (2021).
  * [8] S.-K. Liao, W.-Q. Cai, W.-Y. Liu, L. Zhang, Y. Li, J.-G. Ren, J. Yin, Q. Shen, Y. Cao, Z.-P. Li _et al._ , “Satellite-to-ground quantum key distribution,” Nature 549, 43–47 (2017).
  * [9] J.-G. Ren, M. Abulizi, H.-L. Yong, J. Yin, X.-J. Li, Y. Jiang, W.-Y. Wang, H.-J. Xue, Y.-H. Chen, B. Jin _et al._ , “Portable ground stations for space-to-ground quantum key distribution,” arXiv preprint arXiv:2205.13828 (2022).
  * [10] C.-Y. Lu, Y. Cao, C.-Z. Peng, and J.-W. Pan, “Micius quantum experiments in space,” Reviews of Modern Physics 94, 035001 (2022).
  * [11] H. Takesue, S. W. Nam, Q. Zhang, R. H. Hadfield, T. Honjo, K. Tamaki, and Y. Yamamoto, “Quantum key distribution over a 40-db channel loss using superconducting single-photon detectors,” Nature photonics 1, 343–348 (2007).
  * [12] S. Wang, W. Chen, J.-F. Guo, Z.-Q. Yin, H.-W. Li, Z. Zhou, G.-C. Guo, and Z.-F. Han, “2 ghz clock quantum key distribution over 260 km of standard telecom fiber,” Optics letters 37, 1008–1010 (2012).
  * [13] H. Shibata, T. Honjo, and K. Shimizu, “Quantum key distribution over a 72 db channel loss using ultralow dark count superconducting single-photon detectors,” Optics letters 39, 5078–5081 (2014).
  * [14] J. F. Dynes, W. W. Tam, A. Plews, B. Fröhlich, A. W. Sharpe, M. Lucamarini, Z. Yuan, C. Radig, A. Straw, T. Edwards _et al._ , “Ultra-high bandwidth quantum secured data transmission,” Scientific reports 6, 1–6 (2016).
  * [15] F. Grünenfelder, A. Boaron, D. Rusca, A. Martin, and H. Zbinden, “Simple and high-speed polarization-based qkd,” Applied Physics Letters 112, 051108 (2018).
  * [16] A. Boaron, B. Korzh, R. Houlmann, G. Boso, D. Rusca, S. Gray, M.-J. Li, D. Nolan, A. Martin, and H. Zbinden, “Simple 2.5 ghz time-bin quantum key distribution,” Applied Physics Letters 112, 171108 (2018).
  * [17] A. Boaron, G. Boso, D. Rusca, C. Vulliez, C. Autebert, M. Caloz, M. Perrenoud, G. Gras, F. Bussières, M.-J. Li _et al._ , “Secure quantum key distribution over 421 km of optical fiber,” Physical review letters 121, 190502 (2018).
  * [18] S. Wang, Z.-Q. Yin, D.-Y. He, W. Chen, R.-Q. Wang, P. Ye, Y. Zhou, G.-J. Fan-Yuan, F.-X. Wang, Y.-G. Zhu _et al._ , “Twin-field quantum key distribution over 830-km fibre,” Nature Photonics 16, 154–161 (2022).
  * [19] J. Yin, Y.-H. Li, S.-K. Liao, M. Yang, Y. Cao, L. Zhang, J.-G. Ren, W.-Q. Cai, W.-Y. Liu, S.-L. Li _et al._ , “Entanglement-based secure quantum cryptography over 1,120 kilometres,” Nature 582, 501–505 (2020).
  * [20] N. Namekata, H. Takesue, T. Honjo, Y. Tokura, and S. Inoue, “High-rate quantum key distribution over 100 km using ultra-low-noise, 2-ghz sinusoidally gated ingaas/inp avalanche photodiodes,” Optics express 19, 10632–10639 (2011).
  * [21] H.-K. Lo, M. Curty, and B. Qi, “Measurement-device-independent quantum key distribution,” Physical review letters 108, 130503 (2012).
  * [22] Z. Tang, Z. Liao, F. Xu, B. Qi, L. Qian, and H.-K. Lo, “Experimental demonstration of polarization encoding measurement-device-independent quantum key distribution,” Physical review letters 112, 190503 (2014).
  * [23] H.-L. Yin, T.-Y. Chen, Z.-W. Yu, H. Liu, L.-X. You, Y.-H. Zhou, S.-J. Chen, Y. Mao, M.-Q. Huang, W.-J. Zhang _et al._ , “Measurement-device-independent quantum key distribution over a 404 km optical fiber,” Physical review letters 117, 190501 (2016).
  * [24] M. Lucamarini, Z. L. Yuan, J. F. Dynes, and A. J. Shields, “Overcoming the rate–distance limit of quantum key distribution without quantum repeaters,” Nature 557, 400–403 (2018).
  * [25] X.-B. Wang, Z.-W. Yu, and X.-L. Hu, “Twin-field quantum key distribution with large misalignment error,” Physical Review A 98, 062323 (2018).
  * [26] C. Cui, Z.-Q. Yin, R. Wang, W. Chen, S. Wang, G.-C. Guo, and Z.-F. Han, “Twin-field quantum key distribution without phase postselection,” Physical Review Applied 11, 034053 (2019).
  * [27] J.-P. Chen, C. Zhang, Y. Liu, C. Jiang, W. Zhang, X.-L. Hu, J.-Y. Guan, Z.-W. Yu, H. Xu, J. Lin _et al._ , “Sending-or-not-sending with independent lasers: Secure twin-field quantum key distribution over 509 km,” Physical review letters 124, 070501 (2020).
  * [28] R. I. Woodward, Y. Lo, M. Pittaluga, M. Minder, T. Paraïso, M. Lucamarini, Z. Yuan, and A. Shields, “Gigahertz measurement-device-independent quantum key distribution using directly modulated lasers,” npj Quantum Information 7, 1–6 (2021).
  * [29] C. Clivati, A. Meda, S. Donadello, S. Virzì, M. Genovese, F. Levi, A. Mura, M. Pittaluga, Z. Yuan, A. J. Shields _et al._ , “Coherent phase transfer for real-world twin-field quantum key distribution,” Nature communications 13, 1–9 (2022).
  * [30] G. Gol’Tsman, O. Okunev, G. Chulkova, A. Lipatov, A. Semenov, K. Smirnov, B. Voronov, A. Dzardanov, C. Williams, and R. Sobolewski, “Picosecond superconducting single-photon optical detector,” Applied physics letters 79, 705–707 (2001).
  * [31] F. Marsili, V. B. Verma, J. A. Stern, S. Harrington, A. E. Lita, T. Gerrits, I. Vayshenker, B. Baek, M. D. Shaw, R. P. Mirin _et al._ , “Detecting single infrared photons with 93% system efficiency,” Nature Photonics 7, 210–214 (2013).
  * [32] Z. Yuan, B. Kardynal, A. Sharpe, and A. Shields, “High speed single photon detection in the near infrared,” Applied Physics Letters 91, 041114 (2007).
  * [33] A. Dixon, Z. Yuan, J. Dynes, A. Sharpe, and A. Shields, “Gigahertz decoy quantum key distribution with 1 mbit/s secure key rate,” Optics express 16, 18790–18797 (2008).
  * [34] C. Marand and P. D. Townsend, “Quantum key distribution over distances as long as 30 km,” Optics Letters 20, 1695–1697 (1995).
  * [35] W. Tittel, J. Brendel, B. Gisin, T. Herzog, H. Zbinden, and N. Gisin, “Experimental demonstration of quantum correlations over more than 10 km,” Physical Review A 57, 3229 (1998).
  * [36] B. Korzh, N. Walenta, R. Houlmann, and H. Zbinden, “A high-speed multi-protocol quantum key distribution transmitter based on a dual-drive modulator,” Optics express 21, 19579–19592 (2013).
  * [37] T. K. Paraïso, I. De Marco, T. Roger, D. G. Marangon, J. F. Dynes, M. Lucamarini, Z. Yuan, and A. J. Shields, “A modulator-free quantum key distribution transmitter chip,” npj Quantum Information 5, 1–6 (2019).
  * [38] I. L. Grande, S. Etcheverry, J. Aldama, S. Ghasemi, D. Nolan, and V. Pruneri, “Adaptable transmitter for discrete and continuous variable quantum key distribution,” Optics Express 29, 14815–14827 (2021).
  * [39] W.-Y. Hwang, “Quantum key distribution with high loss: toward global secure communication,” Physical review letters 91, 057901 (2003).
  * [40] H.-K. Lo, X. Ma, and K. Chen, “Decoy state quantum key distribution,” Physical review letters 94, 230504 (2005).
  * [41] K. Tamaki, M. Curty, G. Kato, H.-K. Lo, and K. Azuma, “Loss-tolerant quantum cryptography with imperfect sources,” Physical Review A 90, 052314 (2014).
  * [42] A. Mizutani, M. Curty, C. C. W. Lim, N. Imoto, and K. Tamaki, “Finite-key security analysis of quantum key distribution with imperfect light sources,” New Journal of Physics 17, 093011 (2015).
  * [43] H.-K. Lo and J. Preskill, “Phase randomization improves the security of quantum key distribution,” arXiv preprint quant-ph/0504209 (2005).
  * [44] D. Rusca, A. Boaron, F. Grünenfelder, A. Martin, and H. Zbinden, “Finite-key analysis for the 1-decoy state qkd protocol,” Applied Physics Letters 112, 171104 (2018).
  * [45] N. T. Islam, C. C. W. Lim, C. Cahall, J. Kim, and D. J. Gauthier, “Provably secure and high-rate quantum key distribution with time-bin qudits,” Science advances 3, e1701491 (2017).
  * [46] I. Vagniluca, B. Da Lio, D. Rusca, D. Cozzolino, Y. Ding, H. Zbinden, A. Zavatta, L. K. Oxenløwe, and D. Bacco, “Efficient time-bin encoding for practical high-dimensional quantum key distribution,” Physical Review Applied 14, 014051 (2020).


# Language Use Matters: Analysis of the Linguistic Structure of Question Texts
Can Characterize Answerability in Quora

Suman Kalyan Maity1, Aman Kharb2 and Animesh Mukherjee3
Department of Computer Science and Engineering
Indian Institute of Technology Kharagpur, India - 721302
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Quora is one of the most popular community Q&A sites of recent times. However,
many question posts on this Q&A site often do not get answered. In this paper,
we quantify various linguistic activities that discriminates an answered
question from an unanswered one. Our central finding is that the way users use
language while writing the question text can be a very effective means to
characterize answerability. This characterization helps us to predict early if
a question remaining unanswered for a specific time period $t$ will eventually
be answered or not and achieve an accuracy of 76.26% ($t=1$ month) and 68.33%
($t=3$ months). Notably, features representing the language use patterns of
the users are most discriminative and alone account for an accuracy of 74.18%.
We also compare our method with some of the similar works (Dror et al., Yang
et al.) achieving a maximum improvement of $\sim 39\%$ in terms of accuracy.

## Introduction

From a group of small users at the time of its inception in 2009, Quora has
evolved in the last few years into one of the largest community driven Q&A
sites with diverse user communities. With the help of efficient content
moderation/review policies and active in-house review team, efficient Quora
bots, this site has emerged into one of the largest and reliable sources of
Q&A on the Internet. On Quora, users can post questions, follow questions,
share questions, tag them with relevant topics, follow topics, follow users
apart from answering, commenting, upvoting/downvoting etc. The integrated
social structure at the backbone of it and the topical organization of its
rich content have made Quora unique with respect to other Q&A sites like Stack
Overflow, Yahoo! Answers etc. and these are some of the prime reasons behind
its popularity in recent times. Quality question posting and getting them
answered are the key objectives of any Q&A site. In this study we focus on the
answerability of questions on Quora, i.e., whether a posted question shall
eventually get answered. In Quora, the questions with no answers are referred
to as “open questions”. These open questions need to be studied separately to
understand the reason behind their not being answered or to be precise, are
there any characteristic differences between ‘open’ questions and the answered
ones. For example, the question “What are the most promising advances in the
treatment of traumatic brain injuries?” was posted on Quora on $23^{rd}$ June,
2011 and got its first answer after almost 2 years on $22^{nd}$ April, 2013.
The reason that this question remained open so long might be the hardness of
answering it and the lack of visibility and experts in the domain. Therefore,
it is important to identify the open questions and take measures based on the
types - poor quality questions can be removed from Quora and the good quality
questions can be promoted so that they get more visibility and are eventually
routed to topical experts for better answers.

Characterization of the questions based on question quality requires expert
human interventions often judging if a question would remain open based on
factors like if it is subjective, controversial, open-ended, vague/imprecise,
ill-formed, off-topic, ambiguous, uninteresting etc. Collecting judgment data
for thousands of question posts is a very expensive process. Therefore, such
an experiment can be done only for a small set of questions and it would be
practically impossible to scale it up for the entire collection of posts on
the Q&A site. In this work, we show that appropriate quantification of various
linguistic activities can naturally correspond to many of the judgment factors
mentioned above (see table 2 for a collection of examples). These quantities
encoding such linguistic activities can be easily measured for each question
post and thus helps us to have an alternative mechanism to characterize the
answerability on the Q&A site.

There are several research works done in Q&A focusing on content of posts. ?
exploit community feedback to identify high quality content on Yahoo! Answers.
? use textual features to predict answer quality on Yahoo! Answers. ?,
investigate predictors of answer quality through a comparative, controlled
field study of user responses. ? study the problem of how long questions
remain unanswered. ? propose a prediction model on how many answers a question
shall receive. ? analyze and predict unanswered questions on Yahoo Answers. ?
study question quality in Yahoo! Answers.

## Dataset description

We obtained our Quora dataset (?) through web-based crawls between June 2014
to August 2014. This crawling exercise has resulted in the accumulation of a
massive Q&A dataset spanning over a period of over four years starting from
January 2010 to May 2014. We initiated crawling with 100 questions randomly
selected from different topics so that different genre of questions can be
covered. The crawling of the questions follow a BFS pattern through the
related question links. We obtained 822,040 unique questions across 80,253
different topics with a total of 1,833,125 answers to these questions. For
each question, we separately crawl their revision logs that contain different
types of edit information for the question and the activity log of the
question asker.

## Linguistic activities on Quora

In this section, we identify various linguistic activities on Quora and
propose quantifications of the language usage patterns in this Q&A site. In
particular, we show that there exists significant differences in the
linguistic structure of the open and the answered questions. Note that most of
the measures that we define are simple, intuitive and can be easily obtained
automatically from the data (without manual intervention). Therefore the
framework is practical, inexpensive and highly scalable.

Content of a question text is important to attract people and make them engage
more toward it. The linguistic structure (i.e., the usage of POS tags, the use
of Out-of-Vocabulary words, character usage etc.) one adopts are key factors
for answerability of questions. We shall discuss the linguistic structure that
often represents the writing style of a question asker.

In fig 1(a), we observe that askers of open questions generally use more no.
of words compared to answered questions. To understand the nature of words
(standard English words or chat-like words frequently used in social media)
used in the text, we compare the words with GNU Aspell
dictionary111http://aspell.net/ to see whether they are present in the
dictionary or not. We observe that both open questions and answered questions
follow similar distribution (see fig 1(b)). Part-of-Speech (POS) tags are
indicators of grammatical aspects of texts. To observe how the Part-of-Speech
tags are distributed in the question texts, we define a diversity metric. We
use the standard CMU POS tagger (?) for identifying the POS tags of the
constituent words in the question. We define the POS tag diversity (POSDiv) of
a question $q_{i}$ as follows: $POSDiv(q_{i})=-\sum_{j\in
pos_{set}}p_{j}\times\log(p_{j})$ where $p_{j}$ is the probability of the
$j^{th}$ POS in the set of POS tags. Fig 1(c) shows that the answered
questions have lower POS tag diversity compared to open questions. Question
texts undergo several edits so that their readability and the engagement
toward them are enhanced. It is interesting to identify how far such edits can
make the question different from the original version of it. To capture this
phenomena, we have adopted ROUGE-LCS recall (?) from the domain of text
summarization. Higher the recall value, lesser are the changes in the question
text. From fig 1(d), we observe that open questions tend to have higher recall
compared to the answered ones which suggests that they have not gone through
much of text editing thus allowing for almost no scope of readability
enhancement.

Figure 1:  Comparison of distribution of a) no. of words in the question b)
fraction of In-Vocabulary words c) POS tag diversity d) ROUGE-LCS recall for
open questions vs answered question.

Psycholinguistic analysis:

Table 1: LIWC analysis for open and answered questions.

LIWC category |  Avg. LIWC score for open questions |  Avg. LIWC score for answered questions
---|---|---
Linguistic processes
Function words |  53.4103535493 |  50.6851839369
Pronouns |  12.465131081 |  8.9026143697
Personal pronouns |  2.0535742638 |  3.2504745366
1st person singular |  0.5472352995 |  1.25078055
1st person plural |  0.2264298902 |  0.3101397509
2nd person |  0.8891512047 |  0.9988166386
3rd person singular |  0.0872251454 |  0.1513366764
3rd person plural |  0.3009577218 |  0.538239755
Impersonal pronoun |  10.41145066 |  5.652067286
Articles |  9.5123765347 |  6.8941214189
Adverbs |  1.8814285055 |  4.7420948251
Conjunctions |  2.9557966399 |  5.5545170373
Negation |  0.2122514539 |  0.5633840273
Psychological processes
Social process |  5.1287708853 |  5.7786061901
Friends |  0.0862088064 |  0.113930289
Humans |  0.6565905105 |  0.7599064902
Positive Emotion |  4.6592739777 |  3.237412964
Negative Emotion |  0.6840035078 |  0.8363457191
Anxiety |  0.0840210468 |  0.1076020387
Anger |  0.2170340626 |  0.2476001891
Sadness |  0.1204472445 |  0.1710861523
Cognitive Processes |  10.0861552663 |  15.3887239508
Cause |  1.8814640451 |  5.1099404004
Tentative |  1.997843626 |  3.4358232973
Biological Processes |  1.148483338 |  1.111548769
Body |  0.266928367 |  0.2620352255
Health |  0.4831117881 |  0.477567512
Sexual |  0.0809014124 |  0.0779684738

The way an individual talks or writes, give us clue to his/her linguistic,
emotional, and cognitive states. A question asker’s linguistic, emotional,
cognitive states are also revealed through the language he/she uses in the
question text. In order to capture such psycholinguistic aspects of the asker,
we use Linguistic Inquiry and Word Count (LIWC) (?) that analyzes various
emotional, cognitive, and structural components present in individuals’
written texts. LIWC takes a text document as input and outputs a score for the
input for each of the LIWC categories such as linguistic (part-of-speech of
the words, function words etc.) and psychological categories (social, anger,
positive emotion, negative emotion, sadness etc.) based on the writing style
and psychometric properties of the document. In table 1, we perform a
comparative analysis of the asker’s psycholinguistic state while asking an
open question and an answered question.

Askers of open questions use more function words, impersonal pronouns,
articles on an average whereas asker of answered questions use more personal
pronouns, conjunctions and adverbs to describe their questions. Essentially,
open questions lack content words compared to answered questions which, in
turn, affects the readability of the question. As far as the psychological
aspects are concerned, answered question askers tend to use more social,
family, human related words on average compared to an open question asker. The
open question askers express more positive emotions whereas the answered
question asker tend to express more negative emotions in their texts. Also,
answered question askers are more emotionally involved and their questions
reveal higher usage of anger, sadness, anxiety related words compared to that
of open questions. Open questions, on the other hand, contains more sexual,
body, health related words which might be reasons why they do not attract
answers.

In table 2, we show a collection of examples of open questions to illustrate
that many of the above quantities based on the linguistic activities described
in this section naturally correspond to the factors that human judges consider
responsible for a question remaining unanswered. This is one of the prime
reasons why these quantities qualify as appropriate indicators of
answerability.

Table 2: Examples of open questions w.r.t. various linguistic activities

Open questions |  Linguistic activities |  Characteristics
---|---|---
Why Is Facebook And The Ad Agencies That Make Money Off Facebook Blaming Their Very Clients For The Poor Results Experienced On Facebook’s Platform? Is That Just A Subterfuge? |  high POS tag diversity, lengthy |  too controversial, infuses debates/discussions
How does Max Weinberg feel to be the only person to be both on the last episode of Late Night with David Letterman (as the drummer for guest Bruce Springsteen) and the first episode of Late Night with Conan O’Brien (as the house bandleader)? |  high POS tag diversity, lengthy |  ill-formed, not specific, vague, too many queries jumbled up
If a warehouse of physical goods is seized in the US because of illegal activity by the owner and a few customers using it, are the authorities required to return items that are ”innocent” and were collateral damage once the investigation is complete? |  high POS tag diversity, high ROUGE-LCS score, lengthy |  vague, ill-explained, requires experts to answer
How can Matthew Reilly write such astounding action books? How does he prepare himself while writing a new novel? |  low ROUGE-LCS score |  Very opinionated, difficult to answer
1) How expensive it is to get into Big Data Analytics area with simple service offerings? 2) What is the most simple and popular service provided by companies? I would appreciate an early response on the above or pointers to knowledge sources. |  lengthy, high POS tag diversity |  too many questions, vague/imprecise

## Prediction model

In this section, we describe the prediction framework in detail. Our goal is
to predict whether a given question after a time period $t$ will be answered
or not.
Linguistic styles of the question asker
The content and way of posing a question is important to attract answers. We
have observed in the previous section that these linguistic as well as
psycholinguistic aspects of the question asker are discriminatory factors. For
the prediction, we use the following features:

  * •

Character length of a question, number of words in a question, fraction of
non-frequent words in a question, and number of function words in a question.

  * •

In-Vocabulary (INV) words and Out-of-Vocabulary (OOV) words in question text -
we check whether a word appearing in the question text, is an INV or OOV word
by comparing with GNU Aspell dictionary. We then consider the fraction of INV
words as a feature of our model.

  * •

Presence of n-grams of the question content in English texts - we search for
2, 3, 4 grams of the words from the question text in the corpus of 1 million
contemporary American English
words222http://www.ngrams.info/samples\\_coca1.asp. We use the presence of
bigrams, trigrams, 4-grams each as features.

  * •

POS tag diversity - we use the difference in POS tag diversity between the
initial question text and the question text after time period $t$ (observation
period) as a feature.

  * •

Distribution of LDA topics obtained from question texts - for topic discovery
from the question corpus, we adopt the popular LDA model (?). For a question
$q_{i}$, we consider all the words in that question as a document. We set the
number of topics as K = 10, 20, 30 and find out $p(topic_{k}|D_{i})$ for a
document $D_{i}$ containing all the words of the $i^{th}$ question. Each of
these $p(topic_{k}|D_{i})$ for $k=1..K$ act as a feature.

  * •

LDA topical diversity - we also compute LDA topical diversity ($TopicDiv$) of
a question ($q_{i}$) from the document-topic distributions obtained above as
follows and use this metric as a feature. We define
$TopicDiv(q_{i})=-\sum_{k=1}^{K}p(topic_{k}|D_{i})\times\log
p(topic_{k}|D_{i})$.

  * •

Psycholinguistic aspects of question texts - we consider the LIWC scores from
the different categories as features for the model.

  * •

ROUGE-LCS recall of the question text at the end of the observation period of
the prediction with reference to the original question text posted by the
asker.

Question editing activities: We also consider various editing activities in
questions which could also be a potential source of difference.

  * •

Number of (i) context topic edits, (ii) question text edits, (iii) question
detail edits, (iv) times new topics have been added to the question, (v) times
existing topics have been removed from the question, (vi) times topics added
by users other than the asker, (vii) topic edits done by the Quora review
team, and (viii) other kinds of edits done by the Quora review team.

  * •

Question promotions - A question can be promoted to various users for
increased visibility. We use number of question promotions as well as the
number of people to which it has been promoted as features.

  * •

Average time interval between edits.

Features based on topic hierarchy: Question topics play an important role in
organizing the question and better the organization a question has, better is
its chance of exposure to the experts. In Quora, topics are hierarchically
organized via parent-child relationship in the form of forests with a core
tree. We separately crawl the topic hierarchy of almost all the topics
available in Quora and devise the following features

  * •

Number of topics associated with a question.

  * •

Average depth, maximum depth and variance of depth of the question topics in
the topic hierarchy.

  * •

Maximum number of question topics belonging to the same level in the topic
hierarchy tree.

  * •

Number of connected components of the topic hierarchy graph the question
topics belong to.

  * •

Difference in question topics at the time of question post and the topics
associated with the question after time period $t$ (observation period).

## Performance of the prediction model

We perform our predictions at two time points – $t=1$ month and $t=3$ months
after a question is posted. In other words, for the first (second) case any
question that remains open at the end of one month (three months) is labeled
as ‘open’ in the ground-truth data, else it is labeled ‘answered’. Further, in
the first (second) case, all the features described in the previous section
are calculated only using the one month (three months) observation data.
Restricting the computation of the features to the observation period only
ensures that there is strictly no scope for data leakage.

In the prediction task, we remove all the questions posted by the anonymous
users. We perform a 10-fold cross-validation with SVM classifier and achieve
76.26% accuracy with high avg. precision and recall rates for $t$ = 1 month
and 68.33% for $t$ = 3 months (see table 3 for details). Logistic regression
(LR) and random forest (RF) classifiers yield very similar classification
performance (at $t=1$ month, accuracy of 75.11% and 74.42% for LR and RF
respectively) although SVM performs best among them. Consequently, we report
the performance of the SVM classifier in detail. We observe that the number of
topics ($K$) of LDA does not have a significant effect on the classification
results. For $K=20$, we achieve the best accuracy, avg. precision, recall and
the area under the ROC curve. Note that, as time progresses prediction becomes
harder; thanks to the rich set of features, even with three months observation
period, we are able to obtain a decent prediction accuracy.

There are a very few early works (?; ?) regarding answerability of the
questions and we use them as baseline models. We achieve $\sim 33\%$ and $\sim
39\%$ improvement in terms of accuracy over Yang et al.’s and Dror et al.’s
method respectively for $t=1$ month (see table 3 for further details). Our
method is performing best for prediction on shorter time periods than the
baselines.

Table 3: Performance of various methods ($K$ = 10, 20, 30). First 5 lines for
$t$ = 1 month and last 5 lines for $t$ = 3 months

Method | $K$ | Accuracy | Precision | Recall | F-Score | ROC Area
---|---|---|---|---|---|---
Our Method | 10 | 75.21% | 0.752 | 0.752 | 0.752 | 0.752
20 | 76.26% | 0.763 | 0.763 | 0.763 | 0.762
30 | 76.11% | 0.761 | 0.761 | 0.761 | 0.761
Yang et al. |  | 57.4% | 0.534 | 0.734 | 0.618 | 0.543
Dror et al. |  | 55% | 0.543 | 0.73 | 0.624 | 0.554
Our Method | 10 | 64.3% | 0.643 | 0.643 | 0.643 | 0.643
20 | 68.33% | 0.684 | 0.683 | 0.683 | 0.683
30 | 66.8% | 0.669 | 0.669 | 0.669 | 0.669
Yang et al. |  | 59.3% | 0.587 | 0.64 | 0.613 | 0.592
Dror et al. |  | 59.8% | 0.596 | 0.628 | 0.612 | 0.598

Feature importance: We observe that linguistic style features are the most
discriminative ones achieving an accuracy of 74.18% alone. In order to further
determine the discriminative power of each feature, we compute the $\chi^{2}$
value and the information gain. The most prominent ones among the linguistic
activities are the LIWC features. Some other features that are effective are
the topic hierarchy and the topical edit features.

## Conclusions

In this paper, we investigate various linguistic activities and observe how
such activities affect answerability of questions in Quora. One of the primary
lesson is that the language usage patterns correspond to quality factors that
human judges would consider to decide if a question would remain unanswered.
Based on these linguistic activities we can efficiently discriminate the open
and the answered questions. Our proposed prediction framework achieves an
accuracy of 76.26% ($t=1$ month) and 68.33% ($t=1$ months) with high precision
and recall outperforming the baseline methods convincingly.

## References

  * [Agichtein et al. 2008] Agichtein, E.; Castillo, C.; Donato, D.; Gionis, A.; and Mishne, G.  2008\.  Finding high-quality content in social media.  WSDM ’08, 183–194.
  * [Asaduzzaman et al. 2013] Asaduzzaman, M.; Mashiyat, A. S.; Roy, C. K.; and Schneider, K. A.  2013\.  Answering questions about unanswered questions of stack overflow.  MSR ’13, 97–100.
  * [Blei, Ng, and Jordan 2003] Blei, D. M.; Ng, A. Y.; and Jordan, M. I.  2003\.  Latent dirichlet allocation.  J. Mach. Learn. Res. 3:993–1022.
  * [Dror, Maarek, and Szpektor 2013] Dror, G.; Maarek, Y.; and Szpektor, I.  2013\.  Will my question be answered? predicting “question answerability” in community question-answering sites.  ECML-PKDD ’13.
  * [Harper et al. 2008] Harper, F. M.; Raban, D.; Rafaeli, S.; and Konstan, J. A.  2008\.  Predictors of answer quality in online q&a sites.  CHI ’08, 865–874.
  * [Li et al. 2012] Li, B.; Jin, T.; Lyu, M. R.; King, I.; and Mak, B.  2012\.  Analyzing and predicting question quality in community question answering services.  WWW ’12 Companion, 775–782.
  * [Lin 2004] Lin, C.-Y.  2004\.  Rouge: A package for automatic evaluation of summaries.  In Proc. of ACL-04 workshop, volume 8.
  * [Maity, Sahni, and Mukherjee 2015] Maity, S. K.; Sahni, J. S. S.; and Mukherjee, A.  2015\.  Analysis and prediction of question topic popularity in community q&a sites: A case study of quora.  ICWSM ’15.
  * [Owoputi et al. 2013] Owoputi, O.; Dyer, C.; Gimpel, K.; Schneider, N.; and Smith, N. A.  2013\.  Improved part-of-speech tagging for online conversational text with word clusters.  NAACL ’13.
  * [Pennebaker, Francis, and Booth 2001] Pennebaker, J. W.; Francis, M. E.; and Booth, R. J.  2001\.  Linguistic Inquiry and Word Count.  Mahwah, NJ: Lawerence Erlbaum Associates.
  * [Shah and Pomerantz 2010] Shah, C., and Pomerantz, J.  2010\.  Evaluating and predicting answer quality in community qa.  SIGIR ’10, 411–418.
  * [Yang et al. 2011] Yang, L.; Bao, S.; Lin, Q.; Wu, X.; Han, D.; Su, Z.; and Yu, Y.  2011\.  Analyzing and predicting not-answered questions in community-based question answering services.  AAAI’11, 1273–1278.


# A general scheme for separably reducible properties††thanks: Part of this
article has been done during visits of the third author in Technion, Haifa,
within the framework of a joint project between the Bulgarian Academy of
Sciences and Israeli Academy of Sciences and Humanities

M. Fabian, A. Ioffe and J.P. Revalski  The first author has been supported by
grants GAČR 20-2230L and RVO 67985840.

###### Abstract

We propose a general scheme for studying separably reducible properties in
metric spaces and then apply it to obtain separable determinacy of Lipschitz
property and the separable determinacy of slopes.

2020 Mathematics Subject Classification: Primary: 46B26; 49J52 Secondary:
26E15

Key words and phrases: Separable reduction, cofinal family, rich family,
Lipschitz property, slopes

##  1 Introduction and preliminaries

The aim of this article is to propose a possible general scheme for
investigating the separable reducibility of some properties in a metric space
$(X,d)$. Let us remind that a property ${\cal P}$ considered at the points of
the metric space $X$ is said to be separably reducible (or, equivalently,
separably determined) if there is a family ${\cal F}$ of closed separable
subsets of $X$ such that $\cup\\{Y:Y\in{\cal F}\\}=X$ and for every $Y\in{\cal
F}$ the property ${\cal P}$ is satisfied at $x\in Y$ in $X$ if (and only if)
the ”natural restriction” of ${\cal P}$ on $Y$ is satisfied at $x$. The
restriction of ${\cal P}$ on $Y$ is usually done in an evident way. In such a
situation we also say that ${\cal P}$ is reducible by ${\cal F}$. Roughly,
separable determinacy reduces the verification of some property in the space
$X$ (the latter might not be separable) to the verification of the same
property on separable subsets of $X$. Examples of such separably reducible
properties are some classical properties such as the reflexivity of Banach
spaces, Radon-Nikodým property in Banach spaces, Asplundness of Banach spaces,
Fréchet differentiability of continuous functions in Banach spaces (see [Pr]
for the latter), Fréchet subdifferentiability of functions in Banach spaces
(see [FI1]) and many others (see the book [LPT]).

In this paper we will be interested in separably reducible properties by
families which are even richer than merely covering the underlying spaces.
Namely, a family ${\cal R}$ of closed separable subspaces of $X$ is called
rich (see [BoMo]) if the following two properties are true:

  1. (i)

for every separable subspace $Y_{0}$ of $X$ there is an element $Y\in{\cal R}$
such that $Y_{0}\subset Y$ (cofinality).

  2. (ii)

if $\\{Y_{i}:i\geq 1\\}$ is an increasing sequence of elements of ${\cal R}$
(that is, $Y_{i}\subset Y_{i+1}$ and $Y_{i}\in{\cal R}$ for every $i\geq 1$)
then $Y=\overline{\cup_{i\geq 1}Y_{i}}$ is an element of ${\cal R}$
($\sigma$-closedness).

The terminology rich for such families is justified by the following fact:

###### Proposition 1.1

([BoMo])The intersection of countably many rich families of closed separable
subspaces of $X$ is again a rich family of closed separable subspaces of $X$

Thus, in particular, if we have two distinct properties (or even countably
many properties!) that are separably reducible by rich families, then the
simultaneous satisfaction of all properties is also separably reducible by the
rich family which is the intersection of the corresponding families.
Sometimes, when we are in the setting of a Banach space, the (rich) families
of closed separable subspaces are constituted by closed separable linear
subspaces of $X$.

Results involving separable reducibility by rich families can be found in
[BoMo] (for minimality of Clarke subdifferential and integrability of
Lipschitz functions in Banach spaces), [FI2] (for continuity and Fréchet
subdiffertiability of functions in Banach spaces) in [CF] (for Fréchet
subdiferrentiability in Asplund spaces) and in [FIR] (for metric regularity)
and in many other papers, where the property of separable reducibility is
considered. A number of various examples of separably reducible properties can
be found also in the lecture notes [F].

In this paper we will continue the above lines of research with the
investigation of the separable determinacy by rich families of other important
properties in metric spaces and Banach spaces. Among them are the local
Lipschitz property for functions in such spaces and some functors transforming
functions into another ones (like slopes). To do this, in the next section we
propose a general scheme of separable reducibility which we apply in the
subsequent sections in concrete situations. The paper is an attempt to propose
some unification in these considerations but it is far from being exhaustive
concerning the rich variety of separably determined properties.

##  2 A general aproach for separable determinacy

Let $(X,d)$ be a metric space. As usual, the symbol $B(x,r)$, for $x\in X$ and
$r>0$, will stand for the open ball in $(X,d)$ centered at $x$ and with radius
$r$. Let $(P,\rho)$ be a given separable metric space and fix a countable
dense subset $Q$ of $P$. Put $Z:=X\times P$ and consider on the latter some
usual product metric. In such a setting we will suppose the existence of the
following two mappings with the corresponding properties:

  1. (A1)

There is a set-valued mapping $G:Z\rightrightarrows X^{l}$, for some fixed
positive integer $l\geq 1$, with the property:

    1. (A1.1)

for every $z=(x,p)\in Z$ the set $G(z)$ is nonempty and for any $u\in G(z)$
and any sequence $(x_{n})_{n}\subset X$ which converges to $x$, there is a
sequence $(p_{n})_{n}\subset Q$ such that $p_{n}\to p$ and $u\in
G(z_{n})\subset G(z)$ eventually (here $z_{n}=(x_{n},p_{n})$ for every $n\geq
1$).

  1. (A2)

There is a function $\Phi:Z\times X^{l}\to{\mathbb{R}\cup\\{+\infty\\}}$ such
that for every $z\in Z$ we have:

    1. (A2.1)

for any $u\in G(z)$ if $(z_{n})_{n}\subset Z$ converges to $z$ then
$\Phi(z_{n},u)\to\Phi(z,u)$ (continuity of $\Phi(\cdot,u)$ at $z$ for every
$u\in G(z)$);

    2. (A2.2)

for any nonempty set $A$ which intersects $G(z)$ and for any sequence
$(z_{n})_{n}\subset Z$ which converges to $z$ we have

$\displaystyle\limsup_{z_{n}\to z}\,\,\sup\\{\Phi(z_{n},u):u\in A\cap
G(z)\\}\leq\sup\\{\Phi(z,u):u\in A\cap G(z)\\}.$

We notice that if the continuity of $\Phi(\cdot,u)$ at $z\in Z$ from (A2.1) is
uniform on $u\in A\cap G(z)$, then the condition (A2.2) is fulfilled.

With the above setting we have the following general separable reducibility
result:

###### Theorem 2.1

Let $X$, $P$ and $Q$ be as above. Suppose that (A1) and (A2) are fulfilled
with their sub-properties.

Then the family ${\cal R}$ of closed separable subspaces of $X$ such that for
every $Y\in{\cal R}$, for every $x\in Y$ and for every $p\in P$ we have for
$z=(x,p)$ that $Y^{l}\cap G(z)\neq\emptyset$ and that

$\sup\\{\Phi(z,u):u\in G(z)\\}=\sup\\{\Phi(z,u):u\in Y^{l}\cap G(z)\\}$ $None$

is a rich family.

Proof: We prove first that the family ${\cal R}$ satisfies the condition (i)
(cofinality) of the definition of rich family. To this end, let us, for any
$z=(x,p)\in Z$, fix a countable set $D(z)\subset G(z)$ such that

$\sup\\{\Phi(z,u):u\in G(z)\\}=\sup\\{\Phi(z,u):u\in D(z)\\}.$

Let now $Y_{0}$ be a closed separable subspace of $X$ and $C_{0}$ be a
countable set in $X$ such that $Y_{0}=\overline{C_{0}}$. Put

$C_{1}:=C_{0}\bigcup\Big{\\{}\bigcup_{k=1}^{l}\pi_{k}(D(x,p)):x\in C_{0},p\in
Q\Big{\\}},$

where $\pi_{k}$, $k=1,\ldots,l$, are the canonical projections of $X^{l}$ onto
the $k$-th copy of $X$. Obviously $C_{1}$ is a countable subset of $Y$
containing $C_{0}$. Set $Y_{1}:=\overline{C_{1}}$. Continuing in this way by
induction, we obtain an increasing sequence of countable sets $C_{0}\subset
C_{1}\subset\cdots\subset X$ such that for every $i\geq 0$

$\displaystyle
C_{i+1}:=C_{i}\bigcup\Big{\\{}\bigcup_{k=1}^{l}\pi_{k}(D(x,p)):x\in
C_{i},\,\,p\in Q\Big{\\}}.$

Let $Y_{i}:=\overline{C_{i}}$, $i\geq 0$, and put $Y:=\overline{\cup_{i\geq
0}Y_{i}}=\overline{\cup_{i\geq 0}C_{i}}$. The latter is a closed separable
subspace of $X$ and we will show that $Y\in{\cal R}$. Indeed, let $x\in Y$ and
$p\in P$. We have to prove that $Y^{l}\cap G(z)\neq\emptyset$ and that the
left hand side of (*) is less or equal to the right hand one.

To prove this fix an element $u\in G(z)$ where $z=(x,p)$. Let
$(x_{n})_{n}\subset\cup_{i\geq 0}C_{i}$ be a sequence which converges to $x$.
By condition (A1.1) there is a sequence $(p_{n})_{n}\subset Q$ which converges
to $p$ and we have that for the sequence $z_{n}=(x_{n},p_{n})$, $n\geq 1$,

$u\in G(z_{n})\subset G(z)\mbox{ eventually. }$ $None$

On the other hand, let $i_{n}$ be such that $x_{n}\in C_{i_{n}}$, $n\geq 0$.
Then, by the definition of $C_{i_{n}+1}$, we have that
$\cup_{k=1}^{l}\pi_{k}(D(x_{n},p_{n}))$ belongs to $C_{i_{n}+1}$ and thus,
$D(x_{n},p_{n})$ is contained in $Y^{l}$ for each $n\geq 1$. By (2.1), this,
in particular, implies that $Y^{l}$ intersects $G(z)$. We proved that
$Y^{l}\cap G(z)$ is nonempty.

Further, suppose first that $\Phi(z,u)$ is finite. Fix any ${\varepsilon}>0$.
Let $n$ be so large such that (2.1) is fulfilled and also, using (A2.1) and
(A2.2), that for any such $n$ we have in addition,

$\Phi(z,u)\leq\Phi(z_{n},u)+{\varepsilon}$ $None$

and

$\sup\\{\Phi(z_{n},v):v\in Y^{l}\cap G(z)\\}\leq\sup\\{\Phi(z,v):v\in
Y^{l}\cap G(z)\\}+{\varepsilon}.$ $None$

Then, using the last two inequalities, the fact that $D(x_{n},p_{n})\subset
Y^{l}$ for every $n$, the definition of $D(x_{n},p_{n})$ and that by (2.1) for
$n$ large enough we have $D(x_{n},p_{n})\subset G(z)$, we obtain that the
following chain of inequalities holds true for large $n$:

$\begin{array}[]{ll}\vspace{6pt}\Phi(z,u)&\leq\Phi(z_{n},u)+{\varepsilon}\leq\sup\\{\Phi(z_{n},v):v\in
G(z_{n})\\}+{\varepsilon}\\\ \vspace*{6pt}&=\sup\\{\Phi(z_{n},v):v\in
D(z_{n})\\}+{\varepsilon}\leq\sup\\{\Phi(z_{n},v):v\in Y^{l}\cap
G(z)\\}+{\varepsilon}\\\ \vspace{6pt}&\leq\sup\\{\Phi(z,v):v\in Y^{l}\cap
G(z)\\}+2{\varepsilon}.\end{array}$

Since ${\varepsilon}>0$ was arbitrary this shows that $\Phi(z,u)$ is less or
equal to the right hand side of (*). In the case when $\Phi(z,u)=+\infty$ the
reasoning is similar: For any $M>0$ we have that $\Phi(z_{n},u)>M$ eventually
and then we use the same argument (and chain of inequalities) as above to show
that $\sup\\{\Phi(z,v):v\in Y^{l}\cap G(z)\\}>M$, which, since $M>0$ was
arbitrary, implies the equality in (*).

To prove the second property (ii) ($\sigma$-closedness) from the definition of
rich family suppose that $Y_{1}\subset Y_{2}\subset\cdots\subset X$ is an
increasing sequence of elements from ${\cal R}$. Put $Y:=\overline{\cup_{i\geq
1}Y_{i}}$, which obviously is a closed separable subset of $X$ and let $x\in
Y$ and $p\in P$. Let $u\in G(z)$ (with $z=(x,p)$) be arbitrary. Let
$(x_{n})_{n}\subset\cup_{i\geq 0}Y_{i}$ be a sequence which converges to $x$.
Condition (A1.1) gives the existence of a sequence $(p_{n})_{n}\subset Q$
which converges to $p$ and we have that the sequence $z_{n}=(x_{n},p_{n})$,
$n\geq 1$, satisfies (2.1). Suppose that $x_{n}\in Y_{i_{n}}$ for some
$i_{n}$, $n\geq 1$. Since $Y_{i_{n}}^{l}\cap G(z_{n})\neq\emptyset$ and
$G(z_{n})\subset G(z)$ eventually, we obtain that $Y^{l}\cap
G(z)\neq\emptyset$.

Again, suppose first that $\Phi(z,u)$ is finite and fix any ${\varepsilon}>0$.
Let $n$ be so large that, in addition to (2.1) we have also (2.2) and (2.3)
fulfilled.

Then, having in mind that $Y_{i}\in{\cal R}$ for any $i\geq 1$, we obtain the
following chain of inequalities for large $n$:

$\begin{array}[]{ll}\vspace{6pt}\Phi(z,u)&\leq\Phi(z_{n},u)+{\varepsilon}\leq\sup\\{\Phi(z_{n},v):v\in
G(z_{n})\\}+{\varepsilon}\\\ \vspace{6pt}&=\sup\\{\Phi(z_{n},v):v\in
Y_{i_{n}}^{l}\cap G(z_{n})\\}+{\varepsilon}\leq\sup\\{\Phi(z_{n},v):v\in
Y^{l}\cap G(z)\\}+{\varepsilon}\\\ \vspace{6pt}&\leq\sup\\{\Phi(z,v):v\in
Y^{l}\cap G(z)\\}+2{\varepsilon}\end{array}$

obtaining the desired inequality in (*) since ${\varepsilon}>0$ was arbitrary.
The case when $\Phi(z,u)$ is infinite is treated analogously. The proof is
completed.

■

###### Remark 2.2

Observe that, if we are in the setting of a Banach space $X$ and we want to
work only with closed separable linear subspaces of $X$, then in the above
constructions we simply have to consider instead of $C_{i}$ the sets
$C_{i}^{\prime}$ which consist of all rational linear combinations of elements
from $C_{i}$.

We have a ”dual version” of the above result replacing the supremum with
infimum provided we suppose instead of (A2.2) the following property:

  1. (A2.2′)

for any nonempty set $A$ which intersects $G(z)$ and for any sequence
$(z_{n})_{n}\subset Z$ which converges to $z$ we have

$\displaystyle\liminf_{z_{n}\to z}\,\,\inf\\{\Phi(z_{n},u):u\in A\cap
G(z)\\}\geq\inf\\{\Phi(z,u):u\in A\cap G(z)\\}.$

Then, with similar arguments we can prove the following general separable
reducibility result:

###### Theorem 2.3

Let $X$, $P$ and $Q$ be as above. Suppose that (A1) and (A2) are fulfilled
with their sub-properties replacing (A2.2) with (A2.2′) and supposing that
$\Phi$ is with values in $\mathbb{R}\cup\\{-\infty\\}$. Then the family ${\cal
R}$ of closed separable subspaces of $X$ such that for every $Y\in{\cal R}$,
for every $x\in Y$ and for every $p\in P$ we have for $z=(x,p)$ that
$Y^{l}\cap G(z)\neq\emptyset$ and that

$\inf\\{\Phi(z,u):u\in G(z)\\}=\inf\\{\Phi(z,u):u\in Y^{l}\cap G(z)\\}$ $None$

is a rich family

At the end of this section we will investigate separable reducibility in the
above general form when the space $X$ is of the form of Cartesian product
$X=X_{1}\times X_{2}$, where $(X_{1},d_{1})$ and $(X_{2},d_{2})$ are two
metric spaces and on $X$ we consider some usual product metric generated by
$d_{1}$ and $d_{2}$. In particular, we will see that in such a case we can
restrict ourselves to take rich families consisting only of elements of the
form $Y_{1}\times Y_{2}$, where $Y_{i}\in{\cal S}(X_{i})$, $i=1,2$. Namely, we
have the following result:

###### Theorem 2.4

Let $P$ and $Q$ be as above and let $X=X_{1}\times X_{2}$, where
$(X_{1},d_{1})$ and $(X_{2},d_{2})$ are metric spaces. Suppose that
$G:X_{1}\times P\rightrightarrows X_{1}^{l}$ is a mapping satisfying (A1) with
respect to $Z:=X_{1}\times P$. Let $\Phi:Z\times X_{1}^{l}\times
X_{2}\to{\mathbb{R}\cup\\{+\infty\\}}$ be a function such that for every $y\in
X_{2}$ the function $\Phi(\cdot,\cdot,y)$ satisfies (A2.1) and (A2.2) with
respect $Z$, and in addition for every $z\in Z$ the function $\Phi(z,u,\cdot)$
is continuous at any $y\in X_{2}$ uniformly on $u\in G(z)$. Then, the family
${\cal R}$ of closed separable subspaces of $X$ such that every $Y\in{\cal R}$
is of the form $Y=Y_{1}\times Y_{2}$, where $Y_{i}\in{\cal S}(X_{i})$,
$i=1,2$, and, in addition, for every $(x,y)\in Y=Y_{1}\times Y_{2}$ and for
every $p\in P$ we have for $z=(x,p)$ that $Y_{1}^{l}\cap G(z)\neq\emptyset$
and that

$\sup\\{\Phi(z,u,y):u\in G(z)\\}=\sup\\{\Phi(z,u,y):u\in Y_{1}^{l}\cap
G(z)\\}$ $None$

is a rich family.

Proof:

To prove the cofinality of ${\cal R}$, let $Y_{0}$ be a (closed) separable
subspace of $X=X_{1}\times X_{2}$. Then, we can find closed separable
subspaces $Y_{1}^{0}\in{\cal S}(X_{1})$ and $Y_{2}\in{\cal S}(X_{2})$ such
that $Y_{0}\subset Y_{1}^{0}\times Y_{2}$. Take a countable set $C\subset
Y_{2}$ which is dense in $Y_{2}$. For every fixed $y\in C$, let ${\cal R}_{y}$
be the rich family of closed separable subsets of $X_{1}$ which is provided by
Theorem 2.1 for the function $\Phi(\cdot,\cdot,y)$ and which for every
$Y_{1}\in{\cal R}_{y}$, every $x\in Y_{1}$ and $p\in P$ will satisfy
$Y_{1}^{l}\cap G(z)\neq\emptyset$ and (***) for the fixed $y$ and $z=(x,p)$.
Set ${\cal R}^{\prime}:=\cap\\{{\cal R}_{y}:y\in C\\}$. This is a rich family
of closed separable spaces in $X_{1}$ according to Proposition 1.1. Find an
element $Y_{1}\in{\cal R}^{\prime}$ such that $Y_{1}^{0}\subset Y_{1}$. It can
be seen, using the fact that for every $z=(x,p)\in Z$ the function
$\Phi(z,u,\cdot)$ is continuous at any $y\in X_{2}$ uniformly on $u\in G(z)$
that the closed separable subspace $Y_{1}\times Y_{2}$ belongs to ${\cal R}$.

Let us further prove the $\sigma$-completeness of ${\cal R}$. To this end, let
$L_{1}\subset\cdots L_{n}\subset\cdots$ and $M_{1}\subset\cdots\subset
M_{n}\subset\cdots$ be increasing sequences of closed separable subsets of
$X_{1}$ and $X_{2}$ correspondingly, such that $L_{n}\times M_{n}\in{\cal R}$
for every $n\geq 1$. Set $Y_{1}:=\overline{\cup_{n\geq 1}L_{n}}$ and
$Y_{2}:=\overline{\cup_{n\geq 1}M_{n}}$. We will prove that $Y_{1}\times
Y_{2}\in{\cal R}$. Indeed, let $C$ be a dense countable set in $Y_{2}$. Fix
$y\in C$ and let again, ${\cal R}_{y}$ be the rich family provided by Theorem
2.1 for the function $\Phi(\cdot,\cdot,y)$ and which satisfies that for every
$Y_{1}\in{\cal R}_{y}$ and for every $z=(x,p)\in Y_{1}\times P$ the set
$Y_{1}$ intersects $G(z)$ and (***) is true. Then, obviously $L_{n}\in{\cal
R}_{y}$ for every $n\geq 1$ and, therefore, $Y_{1}\in{\cal R}_{y}$ as well,
because ${\cal R}_{y}$ is rich. Now, the property that for every $z=(x,p)\in
Z$ the function $\Phi(z,u,\cdot)$ is continuous at each $y\in X_{2}$ uniformly
on $u\in G(z)$ implies that we have (***) for each $y\in Y_{2}$ and therefore,
$Y_{1}\times Y_{2}$ belongs to ${\cal R}$. The proof is completed.

■

##  3 Separable reducibility of the continuity and the Lipschitz property

In this section we will investigate the separable determiness of the
continuity and the Lipschitz property of functions in metric spaces applying
our general scheme. As we mentioned, the separable reducibility of the
continuity property can be found, say in [FI2]. Here is how it can be derived
from the above general theorems.

###### Theorem 3.1

Let $f:(X,d)\to\mathbb{R}$ be a function defined in the metric space $X$. Then
there is a rich family ${\cal R}$ of closed separable subsets of $X$ such that
for every $Y\in{\cal R}$ and every $x\in Y$ we have

  1. (a)

$\liminf_{y\to x}f(y)=\liminf_{Y\ni y\to x}f(y)$;

  2. (b)

$\limsup_{y\to x}f(y)=\limsup_{Y\ni y\to x}f(y)$;

  3. (c)

$\lim_{y\to x}f(y)=f(x)$ if, and only if, $\lim_{Y\ni y\to x}f(y)=f(x)$.

Proof: To prove (a) we apply Theorem 2.3. Let
$P:=\mathbb{R}_{++}:=\\{r\in\mathbb{R}:r>0\\}$ and $Q$ be the set of all
strictly positive rational numbers. For $Z:=X\times P$ and $z=(x,r)\in Z$, let
$G(z):=B(x,r)$. The mapping $G$ is easily seen to satisfy (A1). Let the
function $\Phi:Z\times X\to\mathbb{R}$ be defined as $\Phi(z,u):=f(u)$,
$z=(x,r)\in Z$, $u\in X$. The verification of (A2.1) and A(2.2′) are
immediate. Therefore, there is a rich family ${\cal R}_{1}$ of closed
separable subsets of $X$ such that for any $Y\in{\cal R}_{1}$, for any $x\in
Y$ and any $r>0$ we have $\inf\\{f(u):u\in B(x,r)\\}=\inf\\{f(u):u\in Y\cap
B(x,r)\\}$. By the definition of $\liminf$ it follows that for every
$Y\in{\cal R}_{1}$ and for any $x\in Y$ we have $\liminf_{y\to
x}f(y)=\liminf_{Y\ni y\to x}f(y)$. In a similar way, using Theorem 2.1 we
obtain a rich family ${\cal R}_{2}$ of closed separable subsets of $X$ such
that for every $Y\in{\cal R}_{2}$ and for any $x\in Y$ we have $\limsup_{y\to
x}f(y)=\limsup_{Y\ni y\to x}f(y)$. To complete the proof, it remains to take
the intersection of the two rich families ${\cal R}:={\cal R}_{1}\cap{\cal
R}_{2}$ which, according to Proposition 1.1, is again a rich family. ■

We continue now with the investigation of the separable determinacy of the
Lipschitz property. We start with the following proposition:

###### Proposition 3.2

Let $f:(X,d)\to\mathbb{R}$ be a function defined in the metric space $X$. Then
there is a rich family ${\cal R}$ of closed separable subsets of $X$ such that
for every $Y\in{\cal R}$, every $x\in Y$ and any $r>0$ we have

$\displaystyle\begin{array}[]{ll}\displaystyle\sup\Bigg{\\{}\frac{|f(u_{1})-f(u_{2})|}{d(u_{1},u_{2})}:u_{1}\neq
u_{2},u_{1},u_{2}\in B(x,r)\Bigg{\\}}=&\\\
\displaystyle\qquad\qquad\qquad\qquad=\sup\Bigg{\\{}\frac{|f(u_{1})-f(u_{2})|}{d(u_{1},u_{2})}:u_{1}\neq
u_{2},u_{1},u_{2}\in Y\cap B(x,r)\Bigg{\\}}.&\\\ \end{array}$

Proof:

The proof is a straightforward application of our Theorem 2.1. Put
$P:=\mathbb{R}_{++}=\\{r\in\mathbb{R}:r>0\\}$ with the usual metric in
$\mathbb{R}$ and let $Q$ be the set of all strictly positive rational numbers.
Let us for $z=(x,r)\in Z:=X\times P$ define $G(z):=\\{(u_{1},u_{2})\in
X^{2}:u_{1}\neq u_{2},u_{1},u_{2}\in B(x,r)\\}$. It is easy to see that $G$
satisfies (A1.1). Let $\Phi:Z\times X^{2}\to\mathbb{R}$ be defined by
$\Phi((x,r),u):=|f(u_{1})-f(u_{2})|/d(u_{1},u_{2})$, where $z=(x,r)\in Z$ and
$u=(u_{1},u_{2})\in X^{2}$. Since the values of $\Phi$ do not depend on $z$,
the conditions (A2.1) and (A2.2) are trivially fulfilled. Thus, it remains to
apply Theorem 2.1 ■

With the above proposition in hand, we can prove that the (local) Lipschitzian
property of a function in $X$ is separably reducible. Using (with simplified
notation) the above used function
$\Phi(u_{1},u_{2}):=|f(u_{1})-f(u_{2})|/d(u_{1},u_{2})$, $u_{1},u_{2}\in X$,
recall that for a function $f:(X,d)\to\mathbb{R}$ the Lipschitz modulus ${\rm
Lip\,}f(x)$ of $f$ at $x\in X$ is defined as

${\rm Lip\,}f(x):=\inf\Bigg{\\{}c>0:\exists
r>0:\,\sup\Big{\\{}\Phi(u_{1},u_{2}):u_{1}\neq u_{2}\in B(x,r)\Big{\\}}\leq
c\Bigg{\\}}.$

The following theorem shows that the local Lipschitz property of a function in
metric spaces is separably reducible. As usual, for a function
$f:X\to\mathbb{R}$ and a set $A\subset X$, the symbol $f|_{A}$ means the
restriction of $f$ on $A$.

###### Theorem 3.3

Let $f:(X,d)\to\mathbb{R}$ be a function defined in $X$. Then there is a rich
family ${\cal R}$ of closed separable subsets of $X$ such that for every
$Y\in{\cal R}$ and every $x\in Y$ we have

${\rm Lip\,}f(x)={\rm Lip\,}(f|_{Y})(x).$

Proof: Given $f$ let ${\cal R}$ be the rich family provided by Proposition
3.2. Let $Y\in{\cal R}$ and $x\in Y$ be fixed. Let $\Phi(\cdot,\cdot)$ be as
above and consider the two sets of possible Lipschitz constants on balls
(centered at $x$) in $X$ and in $Y$ respectively:

$A:=\Big{\\{}c>0:\exists r>0:\sup\\{\Phi(u_{1},u_{2}):u_{1}\neq u_{2}\in
B(x,r)\\}\leq c\Big{\\}}$

and

$A_{Y}:=\Big{\\{}c>0:\exists r>0:\sup\\{\Phi(u_{1},u_{2}):u_{1}\neq u_{2}\in
Y\cap B(x,r)\\}\leq c\Big{\\}}.$

Obviously, $A\subset A_{Y}$ and therefore, $\inf A\geq\inf A_{Y}$ (with the
convention $\inf\emptyset=+\infty$). To prove the inverse inequality, take and
fix some ${\varepsilon}>0$ and suppose $A_{Y}\neq\emptyset$ (otherwise we are
done). Let $\bar{c}\in A_{Y}$ be such that $\bar{c}<\inf A_{Y}+{\varepsilon}$.
Therefore, for some $r>0$ we have

$\sup\\{\Phi(u_{1},u_{2}):u_{1}\neq u_{2}\in Y\cap B(x,r)\\}\leq\bar{c}.$

By Proposition 3.2 we have

$\sup\\{\Phi(u_{1},u_{2}):u_{1}\neq u_{2}\in
B(x,r)\\}=\sup\\{\Phi(u_{1},u_{2}):u_{1}\neq u_{2}\in Y\cap B(x,r)\\}$

and therefore, $\bar{c}\in A$. Consequently, $\inf A\leq\bar{c}<\inf
A_{Y}+{\varepsilon}$ and since ${\varepsilon}>0$ was arbitrary we obtain that
$\inf A\leq\inf A_{Y}$, which completes the proof of the theorem.

■

###### Remark 3.4

If $X$ is a Banach space, then, having in mind Remark 2.2, the seprable
determinacy of the Lipschitz property can be obtained only by closed separable
linear subspaces of $X$.

##  4 Separable reducibility of slopes

Let $(X,d)$ be a metric space and $f:X\to{\mathbb{R}\cup\\{+\infty\\}}$ be a
proper extended real-valued function in it. Recall that the slope of $f$ at
$x\in X$ is given by the expression:

$\displaystyle|\nabla f|(x):=\limsup_{x\neq u\to
x}\frac{(f(x)-f(u))^{+}}{d(x,u)},\qquad x\in X,$

where the symbol $s^{+}$ for a real number $s$ has the usual meaning (0 of
$s\leq 0$ and $s$ otherwise) and we adopt the convention $+\infty-\infty=0$.
We will show that the slope of a function is a functor which is separably
reducible by rich families of closed separable sets in $X$. By this we simply
mean that if $Y$ is a member of such a family and $x\in Y$ then $|\nabla
f|(x)=|\nabla(f|_{Y})|(x)$. To prove it, we need the following proposition
which is a consequence of our main theorem. Below, given a point $x\in X$ and
real positive numbers $r,s$ such that $0<r<s$ we denote by $T(x,r,s):=\\{u\in
X:r<d(x,u)<s\\}$ the torus in $X$ generated by these parameters.

###### Proposition 4.1

Let $f:X\to{\mathbb{R}\cup\\{+\infty\\}}$ be a proper extended-real valued
function in $X$. Then the family ${\cal R}$ of closed separable sets in $X$
such that for every $Y\in{\cal R}$, for every $x\in Y$, for every
$t\in\mathbb{R}$ and every $r,s$ with $0<r<s$ we have $Y\cap
T(x,r,s)\neq\emptyset$ and

$\sup\Bigg{\\{}\frac{(t-f(u))^{+}}{d(x,u)}:u\in
T(x,r,s)\Bigg{\\}}=\sup\Bigg{\\{}\frac{(t-f(u))^{+}}{d(x,u)}:u\in Y\cap
T(x,r,s)\Bigg{\\}}$

is a rich family.

Proof: To apply our general theorem, let
$P:=\\{(t,r,s)\in\mathbb{R}^{3}:0<r<s\\}$ with the inherited standard metric
from $\mathbb{R}^{3}$. Consider as $Q$ the triples $(t,r,s)$ belonging to $P$
whose coordinates are rational numbers. Let $Z:=X\times P$ and for $Z\ni
z=(x,p)\in X\times P$, $p=(t,r,s)$, define $G:Z\rightrightarrows X$ by
$G(z):=T(x,r,s)$. It is easily seen that the so defined $G$ satisfies (A1.1).
Define now the function $\Phi:Z\times X\to{\mathbb{R}\cup\\{+\infty\\}}$ by

$\Phi(z,u):=\frac{(t-f(u))^{+}}{d(x,u)},\qquad z=(x,(t,r,s))\in Z,u\in X.$

Observe that for $z=(x,(t,r,s))\in Z$ and $u\in G(z)$ the distance $d(x,u)$ is
always greater than $r>0$. Therefore, for any $u\in G(z)$ the function
$\Phi(\cdot,u)$ is continuous at $z\in Z$, thus (A2.1) is fulfilled. To check
(A2.2), take $z\in Z$ and let $A$ be a subset of $X$ intersecting $G(z)$. If
$\sup\\{\Phi(z,u):u\in A\cap G(z)\\}=+\infty$ then (A2.2) is obviously
satisfied. If the latter supremum is finite then this implies, in particular,
that $f$ is bounded below on $A\cap G(z)$ (remember that $0<r<d(x,u)<s$ for
any $u\in G(z)$). In the latter case it can be seen that $\Phi(\cdot,u)$ is
continuous in $z$ uniformly on $u\in A\cap G(z)$. But in this situation, as it
was mentioned after the formulation of (A2.2), the latter property is
satisfied. Therefore, we can apply our Theorem 2.1 to get the conclusion of
the proposition, which completes the proof.

■

Having in mind the above, we can prove the separable determiness of slopes.

###### Theorem 4.2

Let $(X,d)$ be a metric space and $f:X\to{\mathbb{R}\cup\\{+\infty\\}}$ be a
proper extended real-valued function in $X$. Then there is a rich family
${\cal R}$ of closed separable sets in $X$ such that for every $Y\in{\cal R}$
and for every $x\in Y$ we have

$|\nabla f|(x)=|\nabla(f|_{Y})|(x).$

Proof: Let ${\cal R}$ be the rich family provided by the previous proposition.
Then for every $Y\in{\cal R}$ and $x\in Y$ we have

$\begin{array}[]{ll}|\nabla
f|(x)&\displaystyle=\inf_{s>0}\sup_{r\in(0,s)}\sup\Bigg{\\{}\frac{(f(x)-f(u))^{+}}{d(x,u)}:u\in
T(x,r,s)\Bigg{\\}}\\\
&\displaystyle=\inf_{s>0}\sup_{r\in(0,s)}\sup\Bigg{\\{}\frac{(f(x)-f(u))^{+}}{d(x,u)}:u\in
Y\cap T(x,r,s)\Bigg{\\}}=|\nabla(f|_{Y})|(x),\\\ \end{array}$

Indeed, when $x\in{\rm dom}f$ this is immediate from the previous proposition.
To see that it is true also for $x\notin{\rm dom}f$, let us just observe that
the previous proposition shows also that the case ${\rm dom}f\cap
T(x,r,s)\neq\emptyset$ and ${\rm dom}f\cap Y\cap T(x,r,s)=\emptyset$ is not
possible and thus, we have that both inner supremums above are either 0 or
$+\infty$.

■

We continue with the study of the separable reducibility of slopes in the
following setting. Let $(X_{1},d_{1})$ and $(X_{2},d_{2})$ be two metric
spaces and $f:X_{1}\times X_{2}\to\mathbb{R}$ be an extended real-valued
function on the Cartesian product of these two spaces, which is Lipschitz in
the second variable, in a sense that there is $k>0$ such that

$|f(x,y^{\prime})-f(x,y^{\prime\prime})|\leq
k\,\,d_{2}(y^{\prime},y^{\prime\prime}),\qquad\mbox{for every }x\in X_{1}.$

On the Cartesian product $X_{1}\times X_{2}$ we consider some usual product
metric generated by $d_{1}$ and $d_{2}$. Then, we have the following theorem:

###### Theorem 4.3

Let $(X_{1},d_{1})$, $(X_{2},d_{2})$ and $f:X_{1}\times X_{2}\to\mathbb{R}$ be
as above. Then there is a rich family ${\cal R}$ of separable subspaces of
$X_{1}\times X_{2}$ of the form $Y_{1}\times Y_{2}$, $Y_{i}\in{\cal
S}(X_{i})$, $i=1,2$, such that for every $Y_{1}\times Y_{2}\in{\cal R}$, and
for every $(x,y)\in Y_{1}\times Y_{2}$ we have $|\nabla
f(\cdot,y)|(x)=|\nabla(f|_{Y_{1}\times Y_{2}})(\cdot,y)|(x)$.

Proof: Let $d$ be some product metric in $X:=X_{1}\times X_{2}$. We proceed
first as in the proof of Proposition 4.1: let
$P:=\\{(t,r,s)\in\mathbb{R}^{3}:0<r<s\\}$ and $Q$ be the set of the rational
triples $(t,r,s)$ belonging to $P$. Let $Z:=X_{1}\times P$ and for $Z\ni
z=(x,p)\in X_{1}\times P$, $p=(t,r,s)$, define $G:Z\rightrightarrows X_{1}$ by
$G(z):=T(x,r,s)$, the latter being the corresponding torus in $X_{1}$. The
mapping $G$ satisfies (A1.1). Define the function $\Phi:Z\times X_{1}\times
X_{2}\to{\mathbb{R}\cup\\{+\infty\\}}$ by

$\Phi(z,u,y):=\frac{(t-f(u,y))^{+}}{d_{1}(x,u)},\qquad z=(x,(t,r,s))\in
Z,\,u\in X_{1},\,y\in X_{2}.$

It can be easily seen, using the Lipschitz property of $f$ wrt to the second
variable, that for every $z\in Z$ the function $\Phi(z,u,\cdot)$ is continuous
at each $y\in X_{2}$ uniformly on $u\in G(z)$. As in the proof of Proposition
4.1, for every fixed $y\in Y_{2}$, the function $\Phi(\cdot,\cdot,y)$
satisfies (A2.1) and (A2.2). Then, by Theorem 2.4, there is a rich family
${\cal R}$ of separable subspaces of $X$ of the form $Y_{1}\times Y_{2}$,
$Y_{i}\in{\cal S}(X_{i})$, $i=1,2$, such that for every $Y_{1}\times
Y_{2}\in{\cal R}$, for any $(x,y)\in Y_{1}\times Y_{2}$ and for any
$(t,r,s)\in P$ we have

$\sup\Bigg{\\{}\frac{(t-f(u,y)^{+}}{d_{1}(x,u)}:u\in
T(x,r,s)\Bigg{\\}}=\sup\Bigg{\\{}\frac{(t-f(u,y))^{+}}{d_{1}(x,u)}:u\in
Y_{1}\cap T(x,r,s)\Bigg{\\}}.$

Further, the proof follows the steps from the proof of the previous theorem. ■

## References

  * [BoMo] J. Borwein and W. Moors, Seprable dterminantion of integrability and minimality of the Clark subdifferential mapping, Proc. Amer. Math. Soc., 128(2000), 215–221.
  * [CF] M. Cúth and M. Fabian, Asplund spaces characterized by rich families and separable reduction of Fréchet subdifferentiabuility, J. Func. Anal., 270, Issue 4, (2016), 1361–1378.
  * [F] M. Fabian, Separable reductions and rich families in theory of the Fréchet subdifferentials, Lecture notes, Spring scool on variational analysis, Paseky nad Jizerou, Chech Republic, April 19–25, 2015.
  * [FI1] M. Fabian and A. Ioffe, Seprable reduction in the theory of Fréchet subdifferentials, Set-Valued and Variational Anal., 21(2013), 661–671
  * [FI2] M. Fabian and A. Ioffe, Seprable reductions and rich families in theory of Fréchet subdifferentials, J. Convex Anal., 23(2016), 631–648.
  * [FIR] M. Fabian, A. Ioffe and J.P. Revalski, Separable reduction of local metric regularity, Proc. Amer. Math. Soc., 146 (2018), 5157–5167.
  * [LPT] J. Lindenstrauss, D. Preiss, and J. Tišer, Fréchet differentiability of Lipschitz functions and porous sets in Banach spaces, Ann. Math. Studies no. 179, Princeton University Press 2012.
  * [Pr] D. Preiss, Gâteaux differentiable functions are somewhere Fréchet differentiable, Rend. Circ. Math. Palermo, 33(1984), 122–133.

M.Fabian
Institute of Mathematics, Czech Academy of Sciences, Žitná 25, 115 67 Prague,
Czech Republic
e-mail<EMAIL_ADDRESS>

A. Ioffe
Department of Mathematics, Technion-Israel Institute of Technology, Haifa
32000, Israel
e-mail<EMAIL_ADDRESS>

J.P. Revalski
Institute of Mathematics and Informatics, Bulgarian Academty of Sciences,
Acad. G. Bonchev str., block 8, 1113 Sofia, Bulgaria
and
Bulgarian Academy of Sciences, 1, 15th November str., 1040 Sofia, Bulgaria
e-mail<EMAIL_ADDRESS>